【BZOJ1500】维修数列（splay）

  1 const oo=1000000000;
  2  
  3 var t:array[0..510000,0..1]of longint;
  4     sum,lx,rx,mx:array[0..510000]of int64;
  5     tag,rev,a,b,fa,id,d,size:array[0..510000]of longint;
  6     q:array[0..510000]of longint;
  7     n,m,i,j,k,x,f,root,cnt,head,tail,s:longint;
  8     ch:ansistring;
  9  
 10 function max(x,y:int64):int64;
 11 begin
 12  if x>y then exit(x);
 13  exit(y);
 14 end;
 15  
 16 procedure swap(var x,y:int64);
 17 var t:int64;
 18 begin
 19  t:=x; x:=y; y:=t;
 20 end;
 21  
 22 procedure pushup(x:longint);
 23 var l,r:longint;
 24 begin
 25  l:=t[x,0]; r:=t[x,1];
 26  sum[x]:=sum[l]+sum[r]+b[x];
 27  size[x]:=size[l]+size[r]+1;
 28  mx[x]:=max(mx[l],mx[r]);
 29  mx[x]:=max(mx[x],rx[l]+lx[r]+b[x]);
 30  lx[x]:=max(lx[l],sum[l]+b[x]+lx[r]);
 31  rx[x]:=max(rx[r],sum[r]+b[x]+rx[l]);
 32 end;
 33  
 34 procedure pushdown(x:longint);
 35 var l,r,tmp:longint;
 36 begin
 37  l:=t[x,0]; r:=t[x,1];
 38  if tag[x]>0 then
 39  begin
 40   rev[x]:=0; tag[x]:=0;
 41   if l>0 then
 42   begin
 43    tag[l]:=1; b[l]:=b[x]; sum[l]:=b[x]*size[l];
 44   end;
 45   if r>0 then
 46   begin
 47    tag[r]:=1; b[r]:=b[x]; sum[r]:=b[x]*size[r];
 48   end;
 49   if b[x]>=0 then
 50   begin
 51    if l>0 then
 52    begin
 53     lx[l]:=sum[l]; rx[l]:=sum[l]; mx[l]:=sum[l];
 54    end;
 55    if r>0 then
 56    begin
 57     lx[r]:=sum[r]; rx[r]:=sum[r]; mx[r]:=sum[r];
 58    end;
 59   end
 60   else
 61   begin
 62    if l>0 then
 63    begin
 64     lx[l]:=0; rx[l]:=0; mx[l]:=b[x];
 65    end;
 66    if r>0 then
 67    begin
 68     lx[r]:=0; rx[r]:=0; mx[r]:=b[x];
 69    end;
 70   end;
 71  end;
 72  if rev[x]>0 then
 73  begin
 74   rev[x]:=rev[x] xor 1; rev[l]:=rev[l] xor 1; rev[r]:=rev[r] xor 1;
 75   //tmp:=lx[l]; lx[l]:=rx[l]; rx[l]:=tmp;
 76   //tmp:=lx[r]; lx[r]:=rx[r]; rx[r]:=tmp;
 77   tmp:=t[l,0]; t[l,0]:=t[l,1]; t[l,1]:=tmp;
 78   tmp:=t[r,0]; t[r,0]:=t[r,1]; t[r,1]:=tmp;
 79  
 80   swap(lx[l],rx[l]); swap(lx[r],rx[r]);
 81  // swap(t[l,0],t[l,1]); swap(t[r,0],t[r,1]);
 82  end;
 83 end;
 84  
 85 procedure rotate(x:longint;var k:longint);
 86 var y,z,l,r:longint;
 87 begin
 88  y:=fa[x]; z:=fa[y];
 89  if t[y,0]=x then l:=0
 90   else l:=1;
 91  r:=l xor 1;
 92  if y<>k then
 93  begin
 94   if t[z,0]=y then t[z,0]:=x
 95    else t[z,1]:=x;
 96  end
 97   else k:=x;
 98  fa[t[x,r]]:=y; fa[x]:=z; fa[y]:=x;
 99  t[y,l]:=t[x,r]; t[x,r]:=y;
100  pushup(y);
101  pushup(x);
102 end;
103  
104 procedure splay(x:longint;var k:longint);
105 var y,z:longint;
106 begin
107  while x<>k do
108  begin
109   y:=fa[x]; z:=fa[y];
110   if y<>k then
111   begin
112    if (t[y,0]=x)xor(t[z,0]=y) then rotate(x,k)
113     else rotate(y,k);
114   end
115    else k:=x;
116   rotate(x,k);
117  end;
118 end;
119  
120 procedure build(l,r,x:longint);
121 var mid,now,last:longint;
122 begin
123  if l>r then exit;
124  mid:=(l+r)>>1; now:=id[mid]; last:=id[x];
125  if l=r then
126  begin
127   sum[now]:=a[l]; size[now]:=1;
128   tag[now]:=0; rev[now]:=0;
129   if a[l]>=0 then
130   begin
131    lx[now]:=a[l]; rx[now]:=a[l]; mx[now]:=a[l];
132   end
133    else
134    begin
135     lx[now]:=0; rx[now]:=0; mx[now]:=a[l];
136    end;
137  end
138   else
139   begin
140    build(l,mid-1,mid);
141    build(mid+1,r,mid);
142   end;
143  b[now]:=a[mid]; fa[now]:=last;
144  pushup(now);
145  if mid>=x then t[last,1]:=now
146   else t[last,0]:=now;
147 end;
148  
149 function find(x,k:longint):longint;
150 var l,r:longint;
151 begin
152  pushdown(x);
153  l:=t[x,0]; r:=t[x,1];
154  if size[l]+1=k then exit(x);
155  if size[l]+1>k then exit(find(l,k))
156   else exit(find(r,k-size[l]-1));
157 end;
158  
159 procedure clear(x:longint);
160 var l,r:longint;
161 begin
162  if x=0 then exit;
163  l:=t[x,0]; r:=t[x,1];
164  clear(l); clear(r);
165  inc(tail); q[tail mod 510000]:=x; //队列，记录以前用过但现在已经被删除，可以使用的编号

166  fa[x]:=0; t[x,0]:=0; t[x,1]:=0;
167  tag[x]:=0; rev[x]:=0;
168 end;
169  
170 function split(k,tot:longint):longint;
171 var x,y:longint;
172 begin
173  x:=find(root,k); y:=find(root,k+tot+1);
174  splay(x,root); splay(y,t[x,1]);
175  exit(t[y,0]);
176 end;
177  
178 procedure query(k,tot:longint);
179 var x:longint;
180 begin
181  x:=split(k,tot);
182  writeln(sum[x]);
183 end;
184  
185 procedure del(k,tot:longint);
186 var x,y:longint;
187 begin
188  x:=split(k,tot); y:=fa[x];
189  clear(x); t[y,0]:=0;
190  pushup(y);
191  pushup(fa[y]);
192 end;
193  
194 procedure change(k,tot,v:longint);
195 var x,y:longint;
196 begin
197  x:=split(k,tot); y:=fa[x];
198  b[x]:=v; tag[x]:=1; sum[x]:=size[x]*v;
199  if v>=0 then
200  begin
201   lx[x]:=sum[x]; rx[x]:=sum[x]; mx[x]:=sum[x];
202  end
203   else
204   begin
205    lx[x]:=0; rx[x]:=0; mx[x]:=v;
206   end;
207  pushup(y);
208  pushup(fa[y]);
209 end;
210  
211 procedure rever(k,tot:longint);
212 var x,y,tmp:longint;
213 begin
214  x:=split(k,tot); y:=fa[x];
215  if tag[x]=0 then
216  begin
217   rev[x]:=rev[x] xor 1;
218   tmp:=t[x,0]; t[x,0]:=t[x,1]; t[x,1]:=tmp;
219  // swap(t[x,0],t[x,1]);
220   swap(lx[x],rx[x]);
221   pushup(y);
222   pushup(fa[y]);
223  end;
224 end;
225  
226 procedure ins(k,tot:longint);
227 var x,y,z,i:longint;
228 begin
229  for i:=1 to tot do
230   if tail>=head then begin id[i]:=q[head mod 510000]; inc(head); end //垃圾回收
231    else begin inc(cnt); id[i]:=cnt; end;
232  build(1,tot,0); z:=id[(tot+1)>>1];
233  x:=find(root,k+1); y:=find(root,k+2);
234  splay(x,root); splay(y,t[x,1]);
235  fa[z]:=y; t[y,0]:=z;
236  pushup(y);
237  pushup(x);
238 end;
239  
240 begin
241   
242  readln(n,m);
243  head:=1; tail:=0;
244  mx[0]:=-oo; a[1]:=-oo; a[n+2]:=-oo;
245  for i:=2 to n+1 do read(a[i]);
246  readln;
247  for i:=1 to n+2 do id[i]:=i;
248  build(1,n+2,0);
249  root:=(n+3)>>1; cnt:=n+2;
250  for i:=1 to m do
251  begin
252   for j:=1 to 5 do d[j]:=0;
253   readln(ch); s:=0;
254   k:=length(ch); f:=1; x:=0;
255   for j:=1 to k do
256   begin
257    if (ch[j]>=‘A‘)and(ch[j]<=‘Z‘)or((ch[j]=‘-‘)and(s=0)) then continue;
258    if ch[j]=‘ ‘ then
259    begin
260     if s>0 then d[s]:=f*x;
261     inc(s);
262     x:=0; f:=1;
263     continue;
264    end;
265    if ch[j]=‘-‘ then
266    begin
267     f:=-1; continue;
268    end;
269    x:=x*10+ord(ch[j])-ord(‘0‘);
270   end;
271   d[s]:=f*x;
272   ch:=copy(ch,1,3);
273   if ch=‘INS‘ then
274   begin
275    for j:=1 to d[2] do a[j]:=d[j+2];
276    ins(d[1],d[2]);
277   end;
278   if ch=‘DEL‘ then del(d[1],d[2]);
279   if ch=‘MAK‘ then change(d[1],d[2],d[3]);
280   if ch=‘REV‘ then rever(d[1],d[2]);
281   if ch=‘GET‘ then
282    if d[2]=0 then writeln(0)
283     else query(d[1],d[2]);
284   if ch=‘MAX‘ then writeln(mx[root]);
285  end;
286  
287 end.