【BZOJ2329】括号修复（splay）

  1 const oo=1000000000;
  2 var t:array[0..500000,0..1]of longint;
  3     sum,size,lmax,lmin,rmax,rmin,rev,tag,flp,a,fa,v:array[0..500000]of longint;
  4     n,m,i,j,k,x,y,z,root,s:longint;
  5     ch:ansistring;
  6 
  7 procedure swap(var x,y:longint);
  8 var t:longint;
  9 begin
 10  t:=x; x:=y; y:=t;
 11 end;
 12 
 13 function max(x,y:longint):longint;
 14 begin
 15  if x>y then exit(x);
 16  exit(y);
 17 end;
 18 
 19 function min(x,y:longint):longint;
 20 begin
 21  if x<y then exit(x);
 22  exit(y);
 23 end;
 24 
 25 procedure pushup(p:longint);
 26 var l,r:longint;
 27 begin
 28  if p=0 then exit;
 29  l:=t[p,0]; r:=t[p,1];
 30  sum[p]:=sum[l]+sum[r]+v[p];
 31  size[p]:=size[l]+size[r]+1;
 32  lmax[p]:=max(lmax[l],
 33           max(sum[l]+v[p],
 34               sum[l]+v[p]+lmax[r]));
 35  lmin[p]:=min(lmin[l],
 36           min(sum[l]+v[p],
 37               sum[l]+v[p]+lmin[r]));
 38  rmax[p]:=max(rmax[r],
 39           max(sum[r]+v[p],
 40               sum[r]+v[p]+rmax[l]));
 41  rmin[p]:=min(rmin[r],
 42           min(sum[r]+v[p],
 43               sum[r]+v[p]+rmin[l]));
 44 end;
 45 
 46 procedure dorev(p:longint);
 47 var l,r:longint;
 48 begin
 49  l:=t[p,0]; r:=t[p,1];
 50  rev[p]:=rev[p] xor 1;
 51  swap(t[p,0],t[p,1]);
 52  swap(lmax[p],rmax[p]);
 53  swap(lmin[p],rmin[p]);
 54 end;
 55 
 56 procedure doflp(p:longint);
 57 var l,r:longint;
 58 begin
 59  l:=t[p,0]; r:=t[p,1];
 60  flp[p]:=flp[p] xor 1;
 61  sum[p]:=-sum[p]; v[p]:=-v[p];
 62  lmax[p]:=-lmax[p]; lmin[p]:=-lmin[p];
 63  swap(lmax[p],lmin[p]);
 64  rmax[p]:=-rmax[p]; rmin[p]:=-rmin[p];
 65  swap(rmax[p],rmin[p]);
 66  tag[p]:=-tag[p];
 67 end;
 68 
 69 procedure dotag(p,d:longint);
 70 var l,r:longint;
 71 begin
 72  l:=t[p,0]; r:=t[p,1];
 73  rev[p]:=0; flp[p]:=0;
 74  v[p]:=d; tag[p]:=d; sum[p]:=d*size[p];
 75  lmax[p]:=max(0,sum[p]);
 76  rmax[p]:=lmax[p];
 77  lmin[p]:=min(0,sum[p]);
 78  rmin[p]:=lmin[p];
 79 end;
 80 
 81 procedure pushdown(p:longint);
 82 var l,r:longint;
 83 begin
 84  l:=t[p,0]; r:=t[p,1];
 85  if rev[p]=1 then
 86  begin
 87   if l>0 then dorev(l);
 88   if r>0 then dorev(r);
 89   rev[p]:=0;
 90  end;
 91  if flp[p]=1 then
 92  begin
 93   if l>0 then doflp(l);
 94   if r>0 then doflp(r);
 95   flp[p]:=0;
 96  end;
 97  if tag[p]<>0 then
 98  begin
 99   if l>0 then dotag(l,tag[p]);
100   if r>0 then dotag(r,tag[p]);
101   tag[p]:=0;
102  end;
103 end;
104 
105 procedure rotate(x:longint;var k:longint);
106 var l,r,y,z:longint;
107 begin
108  y:=fa[x]; z:=fa[y];
109  if t[y,0]=x then l:=0
110   else l:=1;
111  r:=l xor 1;
112  if y<>k then
113  begin
114   if t[z,0]=y then t[z,0]:=x
115    else t[z,1]:=x;
116  end
117   else k:=x;
118  fa[y]:=x; fa[x]:=z; fa[t[x,r]]:=y;
119  t[y,l]:=t[x,r]; t[x,r]:=y;
120  pushup(y);
121  pushup(x);
122 end;
123 
124 procedure splay(x:longint;var k:longint);
125 var y,z:longint;
126 begin
127  while x<>k do
128  begin
129   y:=fa[x]; z:=fa[y];
130   if y<>k then
131   begin
132    if (t[y,0]=x)xor(t[z,0]=y) then rotate(x,k)
133     else rotate(y,k);
134   end
135    else k:=x;
136   rotate(x,k);
137  end;
138 end;
139 
140 function kth(x,k:longint):longint;
141 var tmp:longint;
142 begin
143  pushdown(x);
144  tmp:=size[t[x,0]]+1;
145  if k=tmp then exit(x);
146  if k<tmp then exit(kth(t[x,0],k))
147   else exit(kth(t[x,1],k-tmp));
148 end;
149 
150 function split(l,r:longint):longint;
151 var x,y:longint;
152 begin
153  x:=kth(root,l-1); y:=kth(root,r+1);
154  splay(x,root); splay(y,t[x,1]);
155  exit(t[y,0]);
156 end;
157 
158 function query(l,r:longint):longint;
159 var s,x:longint;
160 begin
161  x:=split(l,r);
162  s:=(-lmin[x]+1) div 2+(rmax[x]+1) div 2;
163  exit(s);
164 end;
165 
166 procedure build(l,r,x:longint);
167 var mid,last,now:longint;
168 begin
169  if l>r then exit;
170  mid:=(l+r)>>1; now:=mid; last:=x;
171  if l=r then
172  begin
173   sum[now]:=a[l]; size[now]:=1;
174   tag[now]:=0; rev[now]:=0; flp[now]:=0;
175   if a[l]>=0 then
176   begin
177    lmax[now]:=a[l]; rmax[now]:=a[l];
178    lmin[now]:=0; rmin[now]:=0;
179   end
180    else
181    begin
182     lmax[now]:=0; rmax[now]:=0;
183     lmin[now]:=a[l]; rmin[now]:=a[l];
184    end;
185  end
186   else
187   begin
188    build(l,mid-1,mid);
189    build(mid+1,r,mid);
190   end;
191  fa[now]:=last; v[now]:=a[mid];
192  pushup(now);
193  if mid>=x then t[last,1]:=now
194   else t[last,0]:=now;
195 end;
196 
197 procedure change(l,r,v:longint);
198 var x,y,k:longint;
199 begin
200  x:=split(l,r); y:=fa[x];
201  dotag(x,v);
202  pushup(y);
203  pushup(fa[y]);
204 end;
205 
206 procedure rever(l,r:longint);
207 var x,y:longint;
208 begin
209  x:=split(l,r); y:=fa[x];
210  dorev(x);
211  pushup(y);
212  pushup(fa[y]);
213 end;
214 
215 procedure invert(l,r:longint);
216 var x,y:longint;
217 begin
218  x:=split(l,r); y:=fa[x];
219  doflp(x);
220  pushup(y);
221  pushup(fa[y]);
222 end;
223 
224 begin
225  assign(input,‘bzoj2329.in‘); reset(input);
226  assign(output,‘bzoj2329.out‘); rewrite(output);
227  readln(n,m);
228  readln(ch);
229  for i:=1 to n do
230   if ch[i]=‘(‘ then a[i+1]:=1
231    else a[i+1]:=-1;
232  lmax[0]:=-oo; rmax[0]:=-oo;
233  lmin[0]:=oo; rmin[0]:=oo;
234  build(1,n+2,0);
235  root:=(n+3)>>1;
236  for i:=1 to m do
237  begin
238   readln(ch); k:=length(ch); s:=0; x:=0; y:=0; z:=0;
239   for j:=1 to k do
240   begin
241    if ch[j]=‘ ‘ then begin inc(s); continue; end;
242    if (ch[j]<‘0‘)or(ch[j]>‘9‘) then continue;
243    if s=1 then x:=x*10+ord(ch[j])-ord(‘0‘);
244    if s=2 then y:=y*10+ord(ch[j])-ord(‘0‘);
245   end;
246   if ch[k]=‘(‘ then z:=1
247    else z:=-1;
248   inc(x); inc(y);
249   case ch[1] of
250    ‘R‘:change(x,y,z);
251    ‘S‘:rever(x,y);
252    ‘I‘:invert(x,y);
253    ‘Q‘:writeln(query(x,y));
254   end;
255  end;
256  close(input);
257  close(output);
258 end.