题目

传送门 to LOJ

传送门 to luogu

思路

这也能想到 $\sqrt{A}$ 吗？不愧是标杆 🙏

当 $d>\sqrt{A}$ 时，最多 $\mathcal{O}(\sqrt{A})$ 轮就会搬空所有砖摞；当 $d⩽\sqrt{A}$ 时，最多处理 $\mathcal{O}(\sqrt{A})$ 个 $b_i\ne 0$ 的砖摞。问题在于快速处理。

当 $d>\sqrt{A}$ 时，只需判断是否结束。用 $\mathcal{O}(\sqrt{A})$ 修改、$\mathcal{O}(1)$ 查询的方式求出 $a_i⩾v$ 的最小 $a_i$ 即可（方法不唯一）。

当 $d⩽\sqrt{A}$ 时，需判断以步长为 $d$ 跳跃时是否存在 “空洞”（没有砖摞被搬完），以及第一个 $b_i\ne 0$ 的位置。后者用 $d>\sqrt{A}$ 的方式即可维护。前者嘛，我用了并查集：对每个 $d$ 都建立序列并查集，当 $[i,i+d)$ 中存在 $a_j$ 时就合并并查集 $i\to (i+d)$ 。实现精细，则它可以用 $\mathcal{O}(T\sqrt{A}+A\sqrt{A}\log A)$ 的时间维护。

序列并查集好像还是 $\mathcal{O}(n\log n)$ 的？好像需要四毛子才能做到 $\mathcal{O}(n)$？

然后就可以查询答案了，查询复杂度 $\mathcal{O}(T\sqrt{A}\log A)$，但毕竟 $\log A$ 是并查集来的，不大。

代码

#include <cstdio> // I am the believer of XJX
#include <iostream> // Almighty XJX yyds!!!
#include <algorithm> // oracle: ZXY yydBUS!!!
#include <cstring> // Huge EggDog devoured me!!!
#include <cctype> // decent XYX yydLONELY!!!
using llong = long long;
# define rep(i,a,b) for(int i=(a); i<=(b); ++i)
# define drep(i,a,b) for(int i=(a); i>=(b); --i)
# define rep0(i,a,b) for(int i=(a); i!=(b); ++i)
inline int readint(){
	int a = 0, c = getchar(), f = 1;
	for(; !isdigit(c); c=getchar()) if(c == '-') f = -f;
	for(; isdigit(c); c=getchar()) a = a*10+(c^48);
	return a*f;
}

const int MAXA = 100000;
struct UFS{
	int fa[MAXA+2]; // value from i
	inline void init(){
		rep(i,1,MAXA+1) fa[i] = i;
	}
	int find(int a){
		if(fa[a] == a) return a;
		return fa[a] = find(fa[a]);
	}
	inline void merge(int a, int b){
		fa[find(a)] = find(b);
	}
};
const int SQRTA = 316;
UFS ufs[SQRTA]; // step length = (i+1)

const int MAXCNT = (MAXA-1)/SQRTA+1;
struct List{
	int nxt[MAXA], first[MAXCNT];
	inline void init(){
		rep0(i,0,MAXCNT) first[i] = MAXA;
		memset(nxt,-1,MAXA<<2); // unset
	}	
	void insert(int v){
		-- v; const int id = v/SQRTA;
		for(int i=id-1; (~i)&&first[i]>v; --i) first[i] = v;
		for(int i=v; i>=id*SQRTA; nxt[i]=v,--i)
			if(~nxt[i] && nxt[i] < v) break; // dead
	}
	inline int findNext(const int &r){
		if(r > MAXA) return MAXA+1; // undefined
		if(~nxt[r-1]) return nxt[r-1]+1;
		return first[(r-1)/SQRTA]+1;
	}
};
List all, good;

namespace bucket{
	const int WHOLE = MAXCNT*SQRTA;
	int presum[WHOLE], blksum[MAXCNT];
	void insert(const int &v, const int &dv){
		const int id = (v-1)/SQRTA, r = (id+1)*SQRTA;
		rep0(i,v-1,r) presum[i] = std::min(presum[i]+dv,MAXA);
		rep0(i,id+1,MAXCNT) blksum[i] = std::min(blksum[i]+dv,MAXA);
	}
	inline int querySum(const int &r){
		if(r > MAXA) return blksum[MAXCNT-1]+presum[WHOLE-1];
		return presum[r-1]+blksum[(r-1)/SQRTA];
	}
	inline int querySum(const int &l, const int &r){
		if(l == 1) return querySum(r);
		return querySum(r)-querySum(l-1);
	}
}

int main(){
	good.init(), all.init();
	rep0(i,0,SQRTA) ufs[i].init();
	for(int T=readint(),op,a,b; T; --T){
		op = readint(), a = readint();
		if(op == 1){ // modification
			all.insert(a), b = readint();
			if(b) good.insert(a), bucket::insert(a,b);
			const int rig = all.findNext(a+1);
			rep0(j,0,SQRTA){ // cover [i,i+j]
				int i = std::min(a,rig-j-1);
				for(; i>0&&i+j>=a; --i){
					if(ufs[j].find(i) != i) break;
					ufs[j].merge(i,i+j+1);
				}
			}
		}
		if(op == 2){ // query
			int ans = 0; bool bad = false;
			int now = 0; // how much removed
			while(a > SQRTA){ // before energy drains away
				const int nxt = all.findNext(now+1);
				bad = (nxt == MAXA+1 || nxt > now+a);
				if(bad){ ++ ans; break; } // last day
				int cost = bucket::querySum(now+1,now+a);
				now += a, a -= cost, ++ ans; // at least 1
			}
			if(bad){ printf("%d\n",ans); continue; }
			while(a > 0){ // still willing to work
				if(all.findNext(now+1) == MAXA+1){
					++ ans; break; // no more to kill
				}
				int nxt = good.findNext(now+1);
				if(nxt == MAXA+1) nxt = MAXA<<1; // be INF
				const int rig = ufs[a-1].find(now+1); // gap
				if(rig+a <= nxt){ // won't meet @a nxt
					ans += (rig-now-1)/a, now = rig-1;
					if(all.findNext(now+1) == MAXA+1
					  || all.findNext(now+1) > now+a)
						++ ans; else ans += 2;
					break; // always ends, but maybe the EOL
				}
				int step = (nxt-now-1)/a+1; // just kill @a nxt
				int cost = bucket::querySum(now+1,now+step*a);
				now += step*a, ans += step, a -= cost; // a long way
			}
			printf("%d\n",ans);
		}
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123

后记

我们的队伍名：小游戏又双叒叕杀穿了 。可是校长去摸鱼了，因为他看不上这种级别的比赛。

终于，快结束的时候，他随意地想了下此题，给出了做法。我赶紧去实现。结果当然是失败的。我感觉我辜负了神助。