以下设 \(B\) 为一个阈值，同时也表示值域分块的块长。
先考虑所有 \(b\) 都不为 \(0\) 的情况。对于一组询问，我们设一个 \(x\) 表示：当前已搬完所有 \(a\leq x\) 的砖。那么每次只可能是以下两种情况之一：
-
有至少一摞砖在当前这个单位时间内被搬完
拿 \(x\) 加上 \(d\)，之后拿 \(d\) 减去 \(\sum_{a_i\in[x+1,x+d+1]}b_i\)。
\(\sum_{a_i\in[x+1,x+d+1]}b_i\) 的计算可以采用值域分块做到修改 \(O(\sqrt n)\)，询问 \(O(1)\)。
-
没有砖搬完
结束此过程。
对于单组询问，我们尝试分析其时间复杂度：
-
\(d > B\)
显然上述 \(1\) 操作最多执行 \(\frac{V}{B}\) 次。
-
\(d\leq B\)
因为我们不关心 \(d=0\) 的情况，所以每个小时 \(d\) 都会减少。即 \(1\) 操作执行不超过 \(B\) 次。
修改只需要维护一下上述值域分块即可。总时间复杂度 \(O(T(B+\frac{T}{B})+V(B+\frac{V}{B}))\)。
但是，原命题中实际存在 \(b=0\) 的情况，也就是上述方法可能会在一些数据下变成 \(O(n)\) 的，那我们又该如何应对？
易发现，复杂度退化只会在 \(d\leq\sqrt V\) 的情况下产生。故而考虑维护一个 \(O(\sqrt n)\) 修改、\(O(1)\) 查询 \(\geq i\) 的第一个非零位置的值域分块。同时对于**每种 \(\leq\sqrt V\) 的 \(d\) **维护一个并查集，以求解 \(d\) 取当前值、\(x\) 为起点，最多能加到达哪里（具体操作见上述操作 \(1\)，可以认为这个维护是在只考虑“如果没有任何一摞砖被搬完，小E就会停止工作”这一条件下进行的）。
于是询问中 \(d\leq B\) 的部分，就可以用这两个数据结构去维护 \(x,d\) 了。
时间复杂度多个 \(\log\)，为并查集的复杂度（注意这里不能用按秩合并）。
点击查看代码
#include <bits/stdc++.h>
#define FL(i, a, b) for(int i = (a); i <= (b); i++)
#define FR(i, a, b) for(int i = (a); i >= (b); i--)
using namespace std;
const int N = 1e5 + 170, C = 650;
int n, L, S;
inline char gc(){
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)? EOF : *p1++;
}
inline int read(){
register char ch = gc(); register int sum = 0;
while(!(ch >= '0' && ch <= '9')) ch = gc();
while(ch >= '0' && ch <= '9') sum = sum * 10 + ch - 48, ch = gc();
return sum;
}
inline void write(int x){
if(x < 10){putchar('0' + x); return;}
write(x / 10), putchar('0' + x % 10);
}
struct B1{
int a[N + 10], t[C];
void Upd(int x, int v){
int b = x / L;
FL(i, x, b * L + L - 1) a[i] += v;
FL(i, b + 1, N / L) t[i] += v;
}
int Qry(int l, int r){
l = min(l, N), r = min(r, N);
return a[r] + t[r / L] - a[l - 1] - t[(l - 1) / L];
}
} b1, b2;
struct B3{
int a[N + 10], t[C];
B3(){fill(a, a + N + 1, 1e9), fill(t, t + C, 1e9);}
void Upd(int x, int v){
int b = x / L;
FL(i, b * L, x) a[i] = min(a[i], v);
FL(i, 0, b - 1) t[i] = min(t[i], v);
}
int Qry(int x){
x = min(x, N); return min(a[x], t[x / L]);
}
} b3;
struct DSU{
int fa[N + 10];
DSU(){FL(i, 0, N) fa[i] = i;}
int F(int x){return fa[x] == x? x : fa[x] = F(fa[x]);}
} u[163];
int main(){
n = read(), L = 160, S = N / L + 1;
FL(id, 1, n){
int op = read(), a, b, d, x = 0, ans = 0;
if(op == 1){
a = read(), b = read();
b1.Upd(a, 1), b2.Upd(a, b);
if(b) b3.Upd(a, a); int r = a;
while(r < min(N, a + L) && !b1.Qry(r + 1, r + 1)) r++;
FL(i, 1, L) FR(j, min(a - 1, r - i), a - i){
if(j + i > N || j < 0 || u[i].fa[j] != j) break;
u[i].fa[j] = j + i;
}
}
else{
d = read();
while(d > 0){
ans++; if(!b1.Qry(x + 1, x + d)) break;
if(d <= L){
int y = min(b3.Qry(x + 1), u[d].F(x));
ans += (y - x - 1) / d, x += (y - x - 1) / d * d;
}
x += d, d -= b2.Qry(x - d + 1, x);
}
write(ans), putchar('\n');
}
}
return 0;
}