自动搬运

查看原文

来自洛谷，原作者为

	zac2010 a vegedog

搬运于2025-08-24 22:36:58，当前版本为作者最后更新于2023-09-09 13:16:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

以下设 $B$ 为一个阈值，同时也表示值域分块的块长。

先考虑所有 $b$ 都不为 $0$ 的情况。对于一组询问，我们设一个 $x$ 表示：当前已搬完所有 $a\leq x$ 的砖。那么每次只可能是以下两种情况之一：

1. 有至少一摞砖在当前这个单位时间内被搬完

   拿 $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)$。

2. 没有砖搬完

   结束此过程。

对于单组询问，我们尝试分析其时间复杂度：

• $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;
}