【BZOJ2329】括号修复(splay)

发布时间:2017-2-4 6:44:03编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"【BZOJ2329】括号修复(splay) ",主要涉及到【BZOJ2329】括号修复(splay) 方面的内容,对于【BZOJ2329】括号修复(splay) 感兴趣的同学可以参考一下。

题意:一个左右括号组成的序列,需要维护以下操作:

1:前后翻转

2:区间值取反

3:区间修改

4:询问某一段区间最少修改几次能变成一段合法序列

n,m<=100000

思路:RYZ作业

如果把(看做1,)看做-1,询问的就是这段区间(-左端开始的最小字段和+1) div 2+(右端开始的最大字段和+1) div 2

因为有反转操作,用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(d,sum[p]); 76  rmax[p]:=lmax[p]; 77  lmin[p]:=min(d,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 begin108  y:=fa[x]; z:=fa[y];109  if t[y,0]=x then l:=0110   else l:=1;111  r:=l xor 1;112  if y<>k then113  begin114   if t[z,0]=y then t[z,0]:=x115    else t[z,1]:=x;116  end117   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 begin127  while x<>k do128  begin129   y:=fa[x]; z:=fa[y];130   if y<>k then131   begin132    if (t[y,0]=x)xor(t[z,0]=y) then rotate(x,k)133     else rotate(y,k);134   end135    else k:=x;136   rotate(x,k);137  end;138 end;139 140 function kth(x,k:longint):longint;141 var tmp:longint;142 begin143  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 begin153  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 begin161  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 begin169  if l>r then exit;170  mid:=(l+r)>>1; now:=mid; last:=x;171  if l=r then172  begin173   sum[now]:=a[l]; size[now]:=1;174   tag[now]:=0; rev[now]:=0; flp[now]:=0;175   if a[l]>=0 then176   begin177    lmax[now]:=a[l]; rmax[now]:=a[l];178    lmin[now]:=0; rmin[now]:=0;179   end180    else181    begin182     lmax[now]:=0; rmax[now]:=0;183     lmin[now]:=a[l]; rmin[now]:=a[l];184    end;185  end186   else187   begin188    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]:=now194   else t[last,0]:=now;195 end;196 197 procedure change(l,r,v:longint);198 var x,y,k:longint;199 begin200  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 begin209  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 begin218  x:=split(l,r); y:=fa[x];219  doflp(x);220  pushup(y);221  pushup(fa[y]);222 end;223 224 begin225  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 do230   if ch[i]='(' then a[i+1]:=1231    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 do237  begin238   readln(ch); k:=length(ch); s:=0; x:=0; y:=0; z:=0;239   for j:=1 to k do240   begin241    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:=1247    else z:=-1;248   inc(x); inc(y);249   case ch[1] of250    '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.

 这个版本左右子段可以为空,取最值的时候还要与0比较,同时初始化也不需要,因为可以取空,初始值就是0

  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(0,max(lmax[l],sum[l]+v[p]+lmax[r])); 33  lmin[p]:=min(0,min(lmin[l],sum[l]+v[p]+lmin[r])); 34  rmax[p]:=max(0,max(rmax[r],sum[r]+v[p]+rmax[l])); 35  rmin[p]:=min(0,min(rmin[r],sum[r]+v[p]+rmin[l])); 36 end; 37   38 procedure dorev(p:longint); 39 begin 40  rev[p]:=rev[p] xor 1; 41  swap(t[p,0],t[p,1]); 42  swap(lmax[p],rmax[p]); 43  swap(lmin[p],rmin[p]); 44 end; 45   46 procedure doflp(p:longint); 47 begin 48  flp[p]:=flp[p] xor 1; 49  sum[p]:=-sum[p]; v[p]:=-v[p]; 50  lmax[p]:=-lmax[p]; lmin[p]:=-lmin[p]; 51  swap(lmax[p],lmin[p]); 52  rmax[p]:=-rmax[p]; rmin[p]:=-rmin[p]; 53  swap(rmax[p],rmin[p]); 54  tag[p]:=-tag[p]; 55 end; 56   57 procedure dotag(p,d:longint); 58 begin 59  rev[p]:=0; flp[p]:=0; 60  v[p]:=d; tag[p]:=d; sum[p]:=d*size[p]; 61  if d>0 then 62  begin 63   lmax[p]:=sum[p]; rmax[p]:=sum[p]; 64   lmin[p]:=0; rmin[p]:=0; 65  end 66   else 67   begin 68    lmax[p]:=0; rmax[p]:=0; 69    lmin[p]:=sum[p]; rmin[p]:=sum[p]; 70   end; 71   72 end; 73   74 procedure pushdown(p:longint); 75 var l,r:longint; 76 begin 77  l:=t[p,0]; r:=t[p,1]; 78  if rev[p]=1 then 79  begin 80   if l>0 then dorev(l); 81   if r>0 then dorev(r); 82   rev[p]:=0; 83  end; 84  if flp[p]=1 then 85  begin 86   if l>0 then doflp(l); 87   if r>0 then doflp(r); 88   flp[p]:=0; 89  end; 90  if tag[p]<>0 then 91  begin 92   if l>0 then dotag(l,tag[p]); 93   if r>0 then dotag(r,tag[p]); 94   tag[p]:=0; 95  end; 96 end; 97   98 procedure rotate(x:longint;var k:longint); 99 var l,r,y,z:longint;100 begin101  y:=fa[x]; z:=fa[y];102  if t[y,0]=x then l:=0103   else l:=1;104  r:=l xor 1;105  if y<>k then106  begin107   if t[z,0]=y then t[z,0]:=x108    else t[z,1]:=x;109  end110   else k:=x;111  fa[y]:=x; fa[x]:=z; fa[t[x,r]]:=y;112  t[y,l]:=t[x,r]; t[x,r]:=y;113  pushup(y);114  pushup(x);115 end;116  117 procedure splay(x:longint;var k:longint);118 var y,z:longint;119 begin120  while x<>k do121  begin122   y:=fa[x]; z:=fa[y];123   if y<>k then124   begin125    if (t[y,0]=x)xor(t[z,0]=y) then rotate(x,k)126     else rotate(y,k);127   end128    else k:=x;129   rotate(x,k);130  end;131 end;132  133 function kth(x,k:longint):longint;134 var tmp:longint;135 begin136  pushdown(x);137  tmp:=size[t[x,0]]+1;138  if k=tmp then exit(x);139  if k<tmp then exit(kth(t[x,0],k))140   else exit(kth(t[x,1],k-tmp));141 end;142  143 function split(l,r:longint):longint;144 var x,y:longint;145 begin146  x:=kth(root,l-1); y:=kth(root,r+1);147  splay(x,root); splay(y,t[x,1]);148  exit(t[y,0]);149 end;150  151 function query(l,r:longint):longint;152 var s,x:longint;153 begin154  x:=split(l,r);155  s:=(-lmin[x]+1) div 2+(rmax[x]+1) div 2;156  exit(s);157 end;158  159 procedure build(l,r,x:longint);160 var mid,last,now:longint;161 begin162  if l>r then exit;163  mid:=(l+r)>>1; now:=mid; last:=x;164  if l=r then165  begin166   sum[now]:=a[l]; size[now]:=1;167   tag[now]:=0; rev[now]:=0; flp[now]:=0;168   if a[l]>=0 then169   begin170    lmax[now]:=a[l]; rmax[now]:=a[l];171    lmin[now]:=0; rmin[now]:=0;172   end173    else174    begin175     lmax[now]:=0; rmax[now]:=0;176     lmin[now]:=a[l]; rmin[now]:=a[l];177    end;178  end179   else180   begin181    build(l,mid-1,mid);182    build(mid+1,r,mid);183   end;184  fa[now]:=last; v[now]:=a[mid];185  pushup(now);186  if mid>=x then t[last,1]:=now187   else t[last,0]:=now;188 end;189  190 procedure change(l,r,v:longint);191 var x,y,k:longint;192 begin193  x:=split(l,r); y:=fa[x];194  dotag(x,v);195  pushup(y);196  pushup(fa[y]);197 end;198  199 procedure rever(l,r:longint);200 var x,y:longint;201 begin202  x:=split(l,r); y:=fa[x];203  dorev(x);204  pushup(y);205  pushup(fa[y]);206 end;207  208 procedure invert(l,r:longint);209 var x,y:longint;210 begin211  x:=split(l,r); y:=fa[x];212  doflp(x);213  pushup(y);214  pushup(fa[y]);215 end;216  217 begin218   219  readln(n,m);220  readln(ch);221  for i:=1 to n do222   if ch[i]='(' then a[i+1]:=1223    else a[i+1]:=-1;224  //a[1]:=oo; a[n+2]:=-oo;225  //lmax[0]:=-oo; rmax[0]:=-oo;226 // lmin[0]:=oo; rmin[0]:=oo;227  build(1,n+2,0);228  root:=(n+3)>>1;229  for i:=1 to m do230  begin231   readln(ch); k:=length(ch); s:=0; x:=0; y:=0; z:=0;232   for j:=1 to k do233   begin234    if ch[j]=' ' then begin inc(s); continue; end;235    if (ch[j]<'0')or(ch[j]>'9') then continue;236    if s=1 then x:=x*10+ord(ch[j])-ord('0');237    if s=2 then y:=y*10+ord(ch[j])-ord('0');238   end;239   if ch[k]='(' then z:=1240    else z:=-1;241   inc(x); inc(y);242   case ch[1] of243    'R':change(x,y,z);244    'S':rever(x,y);245    'I':invert(x,y);246    'Q':writeln(query(x,y));247   end;248  // for j:=1 to n+2 do// write(rev[j],' ',flp[j],' ',tag[j],' ');249                       // write(v[j],' ');250  // writeln;251  end;252   253 end.


上一篇:PHP 将amr音频文件转换为mp3格式
下一篇:php使用PDO连接mysql数据库

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款