BZOJ 4003

Splay又被卡链了…尼玛…

传送门

先把每个人插到他初始所在的堆里,然后从下往上逐级合并,每次删掉挂了的人并更新答案,打标记更新当前堆中的战斗力

凭什么所有PASCAL都要卡着时限过 TAT

这道题我先敲了个Splay…改了一下午然后被三组链的数据卡掉了 = = 尼玛丧心病狂啊

还以为启发式是个多高端的东西…就是一个if语句…

改了好久的Splay也扔在下面了…能搞70分呢…

可并堆


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
program bzoj_4003;
var s:array[0..300000]of record lc,rc,dis:longint; k,mul,plus:int64; end;
l:array[1..300000]of record ed,pre:longint; end;
lst,tree,p,dep,cnt,dea:array[1..300001]of longint;
def,v:array[1..300000]of int64;
a:array[1..300000]of boolean;
n,m,i,tot,t,fa:longint;
procedure link(a,b:longint);
begin
inc(tot);
l[tot].pre:=lst[a];
lst[a]:=tot;
l[tot].ed:=b;
end;
procedure swap(var a,b:longint);
var p:longint;
begin
p:=a;
a:=b;
b:=p;
end;
procedure update(t:longint;mul,plus:int64);
begin
s[t].k:=s[t].k*mul+plus;
s[t].plus:=s[t].plus*mul+plus;
s[t].mul:=s[t].mul*mul;
end;
procedure pushdown(t:longint);
begin
if s[t].lc<>0 then update(s[t].lc,s[t].mul,s[t].plus);
if s[t].rc<>0 then update(s[t].rc,s[t].mul,s[t].plus);
s[t].mul:=1;
s[t].plus:=0;
end;
function merge(a,b:longint):longint;
begin
if (a=0)or(b=0) then exit(a+b);
if s[a].k>s[b].k then swap(a,b);
if (s[a].plus<>0)or(s[a].mul<>1) then pushdown(a);
s[a].rc:=merge(s[a].rc,b);
if s[s[a].lc].dis<s[s[a].rc].dis then swap(s[a].lc,s[a].rc);
s[a].dis:=s[s[a].rc].dis+1;
exit(a);
end;
procedure dfs(t:longint);
var k:longint;
begin
k:=lst[t];
while k<>0 do
begin
dep[l[k].ed]:=dep[t]+1;
dfs(l[k].ed);
tree[t]:=merge(tree[t],tree[l[k].ed]);
k:=l[k].pre;
end;
while (tree[t]<>0)and(s[tree[t]].k<def[t]) do
begin
inc(cnt[t]);
if (s[tree[t]].plus<>0)or(s[tree[t]].mul<>1) then pushdown(tree[t]);
dea[tree[t]]:=t;
tree[t]:=merge(s[tree[t]].lc,s[tree[t]].rc);
end;
if tree[t]=0 then exit;
if a[t] then update(tree[t],v[t],0) else update(tree[t],1,v[t]);
end;
begin
readln(n,m);
for i:=1 to n do read(def[i]);
tot:=0;
for i:=2 to n do
begin
readln(fa,t,v[i]);
link(fa,i);
a[i]:=(t=1);
end;
for i:=1 to n do tree[i]:=0;
for i:=1 to m do
begin
readln(s[i].k,p[i]);
s[i].plus:=0;
s[i].mul:=1;
tree[p[i]]:=merge(tree[p[i]],i);
end;
dep[1]:=1;
for i:=1 to n do cnt[i]:=0;
dfs(1);
for i:=1 to n do writeln(cnt[i]);
for i:=1 to m do writeln(dep[p[i]]-dep[dea[i]]);
end.

Splay启发式合并


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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
program bzoj_4003;
var s:array[0..300000]of record fa,lc,rc,size,num:longint; k,plus,mul:int64; end;
n,m,i,tot,k,top,fa,t:longint;
a:array[1..300000]of boolean;
lst,seq,tree,stk,cnt,dep,dea,st:array[1..300000]of longint;
def,v:array[1..300000]of int64;
atk:int64;
l:array[1..600000]of record ed,pre:longint; end;
procedure swap(var a,b:longint);
var p:longint;
begin
p:=a;
a:=b;
b:=p;
end;
procedure link(a,b:longint);
begin
inc(tot);
l[tot].pre:=lst[a];
lst[a]:=tot;
l[tot].ed:=b;
end;
procedure bfs;
var hd,tl,k:longint;
begin
hd:=0;
tl:=1;
seq[1]:=1;
dep[1]:=1;
while hd<>tl do
begin
inc(hd);
k:=lst[seq[hd]];
while k<>0 do
begin
inc(tl);
seq[tl]:=l[k].ed;
dep[seq[tl]]:=dep[seq[hd]]+1;
k:=l[k].pre;
end;
end;
end;
procedure pushdown(t:longint);
var l,r:longint;
begin
l:=s[t].lc;
r:=s[t].rc;
if s[t].mul<>1 then
begin
if l<>0 then
begin
s[l].mul:=s[l].mul*s[t].mul;
s[l].k:=s[l].k*s[t].mul;
s[l].plus:=s[l].plus*s[t].mul;
end;
if r<>0 then
begin
s[r].mul:=s[r].mul*s[t].mul;
s[r].k:=s[r].k*s[t].mul;
s[r].plus:=s[r].plus*s[t].mul;
end;
s[t].mul:=1;
end;
if s[t].plus<>0 then
begin
if l<>0 then
begin
inc(s[l].plus,s[t].plus);
inc(s[l].k,s[t].plus);
end;
if r<>0 then
begin
inc(s[r].plus,s[t].plus);
inc(s[r].k,s[t].plus);
end;
s[t].plus:=0;
end;
end;
procedure l_rotate(t:longint);
var p:longint;
begin
p:=s[t].fa;
s[p].rc:=s[t].lc;
if s[t].lc<>0 then s[s[t].lc].fa:=p;
s[t].fa:=s[p].fa;
if p=s[s[p].fa].lc then s[s[p].fa].lc:=t;
if p=s[s[p].fa].rc then s[s[p].fa].rc:=t;
s[p].fa:=t;
s[t].lc:=p;
s[t].size:=s[p].size;
s[p].size:=s[s[p].lc].size+s[s[p].rc].size+1;
end;
procedure r_rotate(t:longint);
var p:longint;
begin
p:=s[t].fa;
s[p].lc:=s[t].rc;
if s[t].rc<>0 then s[s[t].rc].fa:=p;
s[t].fa:=s[p].fa;
if p=s[s[p].fa].lc then s[s[p].fa].lc:=t;
if p=s[s[p].fa].rc then s[s[p].fa].rc:=t;
s[p].fa:=t;
s[t].rc:=p;
s[t].size:=s[p].size;
s[p].size:=s[s[p].lc].size+s[s[p].rc].size+1;
end;
procedure splay(t:longint);
begin
while s[t].fa<>0 do
if t=s[s[t].fa].lc then r_rotate(t) else l_rotate(t);
end;
procedure insert(var t:longint;k:int64;num:longint);
begin
if t=0 then
begin
if top>0 then
begin
t:=stk[top];
dec(top);
end else
begin
inc(tot);
t:=tot;
end;
s[t].size:=1;
s[t].k:=k;
s[t].num:=num;
s[t].mul:=1;
s[t].plus:=0;
s[t].fa:=0;
s[t].lc:=0;
s[t].rc:=0;
exit;
end;
if (s[t].plus<>0)or(s[t].mul<>1) then pushdown(t);
inc(s[t].size);
if k>=s[t].k then
begin
insert(s[t].lc,k,num);
s[s[t].lc].fa:=t;
end else
begin
insert(s[t].rc,k,num);
s[s[t].rc].fa:=t;
end;
end;
function find(t:longint;k:int64):longint;
begin
find:=t;
while t<>0 do
begin
if (s[t].plus<>0)or(s[t].mul<>1) then pushdown(t);
if k>s[t].k then t:=s[t].lc else
begin
find:=t;
t:=s[t].rc;
end;
end;
end;
function max(t:longint):int64;
begin
while s[t].lc<>0 do
begin
if (s[t].plus<>0)or(s[t].mul<>1) then pushdown(t);
t:=s[t].lc;
end;
exit(s[t].k);
end;
procedure dfs(t,p:longint);
begin
if t=0 then exit;
if (s[t].plus<>0)or(s[t].mul<>1) then pushdown(t);
if s[t].lc<>0 then dfs(s[t].lc,p);
if s[t].rc<>0 then dfs(s[t].rc,p);
insert(p,s[t].k,s[t].num);
inc(top);
stk[top]:=t;
end;
procedure update(t,p:longint);
begin
if t=0 then exit;
if s[t].lc<>0 then update(s[t].lc,p);
if s[t].rc<>0 then update(s[t].rc,p);
cnt[s[t].num]:=dep[st[s[t].num]]-dep[p];
inc(top);
stk[top]:=t;
end;
procedure union(var t1,t2:longint);
begin
if s[t1].size<s[t2].size then swap(t1,t2);
dfs(t2,t1);
end;
procedure maintain(p:longint);
var t:longint;
begin
if tree[p]=0 then exit;
if max(tree[p])>=def[p] then
begin
t:=find(tree[p],def[p]);
splay(t);
tree[p]:=t;
dea[p]:=s[s[t].rc].size;
update(s[t].rc,p);
s[t].rc:=0;
s[t].size:=s[s[t].lc].size+1;
end else
begin
dea[p]:=s[tree[p]].size;
update(tree[p],p);
tree[p]:=0;
exit;
end;
if a[p] then
begin
s[t].mul:=v[p];
s[t].k:=s[t].k*v[p];
end else
begin
inc(s[t].plus,v[p]);
inc(s[t].k,v[p]);
end;
pushdown(t);
end;
begin
readln(n,m);
for i:=1 to n do read(def[i]);
for i:=2 to n do
begin
readln(fa,t,v[i]);
a[i]:=(t=1);
link(fa,i);
end;
bfs;
tot:=0;
top:=0;
for i:=1 to n do tree[i]:=0;
for i:=1 to m do
begin
readln(atk,st[i]);
insert(tree[st[i]],atk,i);
end;
for i:=1 to m do cnt[i]:=dep[st[i]];
for i:=n downto 1 do
begin
k:=lst[seq[i]];
while k<>0 do
begin
union(tree[seq[i]],tree[l[k].ed]);
k:=l[k].pre;
end;
maintain(seq[i]);
end;
for i:=1 to n do writeln(dea[i]);
for i:=1 to m do writeln(cnt[i]);
end.