BZOJ

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.