括号序列的经典做法
把(看成1，）看成-1
匹配的括号序列即任意前缀和都非负
我们先解决静态的问题，给定一段括号序列求最少修改次数
我们先找出最大后缀和a和最小前缀和b
之间一定可以不相交
显然a+|b|个括号是未匹配的
显然修改即为(|b|+1) div 2+(a+1) div 2;
由于序列的变化，我们用splay维护
由于涉及到括号反转我们还要维护左最大和右最小
然后就没了
这个是bzoj2329的代码
var son:array[..,..] of longint;
laz,lmax,rmax,lmin,rmin,size,sum,a,fa:array[..] of longint;
cha,rev:array[..] of boolean;
root,i,n,m,x,y,z,w:longint;
ch:char;
s:string; function min(a,b:longint):longint;
begin
if a>b then exit(b) else exit(a);
end; function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end; procedure swap(var a,b:longint);
var c:longint;
begin
c:=a;
a:=b;
b:=c;
end; procedure get(var a,b:longint);
var c:longint;
begin
c:=a;
a:=-b;
b:=-c;
end; procedure update(x:longint);
var l,r:longint;
begin
l:=son[x,];
r:=son[x,];
size[x]:=size[l]+size[r]+;
sum[x]:=sum[l]+sum[r]+a[x];
lmax[x]:=max(lmax[l],sum[l]+a[x]+lmax[r]);
rmax[x]:=max(rmax[r],sum[r]+a[x]+rmax[l]);
lmin[x]:=min(lmin[l],sum[l]+a[x]+lmin[r]);
rmin[x]:=min(rmin[r],sum[r]+a[x]+rmin[l]);
end; procedure replace(x,w:longint);
begin
a[x]:=w;
laz[x]:=w;
cha[x]:=false;
if w=- then
begin
sum[x]:=-size[x];
lmax[x]:=;
rmax[x]:=;
lmin[x]:=sum[x];
rmin[x]:=sum[x];
end
else begin
sum[x]:=size[x];
lmax[x]:=sum[x];
rmax[x]:=sum[x];
lmin[x]:=;
rmin[x]:=;
end;
end; procedure reverse(x:longint);
begin
swap(son[x,],son[x,]);
swap(lmax[x],rmax[x]);
swap(lmin[x],rmin[x]);
rev[x]:=not rev[x];
end; procedure change(x:longint);
begin
a[x]:=-a[x];
sum[x]:=-sum[x];
get(lmax[x],lmin[x]);
get(rmax[x],rmin[x]);
cha[x]:=not cha[x];
end; procedure push(x:longint);
var l,r:longint;
begin
l:=son[x,];
r:=son[x,];
if laz[x]<> then
begin
if l<>- then replace(l,laz[x]);
if r<>- then replace(r,laz[x]);
laz[x]:=;
end;
if cha[x] then
begin
if l<>- then change(l);
if r<>- then change(r);
cha[x]:=false;
end;
if rev[x] then
begin
if l<>- then reverse(l);
if r<>- then reverse(r);
rev[x]:=false;
end;
end; function find(k:longint):longint;
var p:longint;
begin
p:=root;
while true do
begin
push(p);
if size[son[p,]]+=k then exit(p);
if size[son[p,]]+>k then p:=son[p,]
else begin
k:=k-size[son[p,]]-;
p:=son[p,];
end;
end;
end; procedure rotate(x,w:longint);
var y:longint;
begin
y:=fa[x];
push(x);
if fa[y]=- then root:=x
else begin
if son[fa[y],]=y then son[fa[y],]:=x
else son[fa[y],]:=x;
end;
fa[x]:=fa[y];
son[y,-w]:=son[x,w];
if son[x,w]<>- then fa[son[x,w]]:=y;
son[x,w]:=y;
fa[y]:=x;
update(y);
end; procedure splay(x,f:longint);
var y:longint;
begin
while fa[x]<>f do
begin
y:=fa[x];
if fa[y]=f then
begin
if son[y,]=x then rotate(x,)
else rotate(x,);
end
else begin
if son[fa[y],]=y then
begin
if son[y,]=x then rotate(y,) else rotate(x,);
rotate(x,);
end
else begin
if son[y,]=x then rotate(x,) else rotate(y,);
rotate(x,);
end;
end;
end;
update(x);
end; function getrange(x,y:longint):longint;
begin
x:=find(x);
y:=find(y+);
splay(x,-);
splay(y,x);
exit(son[y,]);
end; function build(l,r:longint):longint;
var m:longint;
begin
m:=(l+r) shr ;
build:=m;
if l<=m- then
begin
son[m,]:=build(l,m-);
fa[son[m,]]:=m;
end;
if m+<=r then
begin
son[m,]:=build(m+,r);
fa[son[m,]]:=m;
end;
update(m);
end; begin
fillchar(fa,sizeof(fa),);
fillchar(son,sizeof(son),);
readln(n,m);
for i:= to n do
begin
read(ch);
if ch='(' then a[i]:= else a[i]:=-;
end;
readln;
root:=build(,n+);
for i:= to m do
begin
read(ch);
s:='';
while ch<>' ' do
begin
s:=s+ch;
read(ch);
end;
read(x,y);
z:=getrange(x,y);
if s='Query' then
writeln((abs(lmin[z])+) div +(rmax[z]+) div )
else if s='Invert' then
begin
if laz[z]= then change(z)
else replace(z,-laz[z]);
end
else if s='Swap' then
reverse(z)
else if s='Replace' then
begin
read(ch);
while not((ch='(') or (ch=')')) do read(ch);
if ch='(' then w:=
else w:=-;
replace(z,w);
end;
readln;
end;
end.