恶心的splay，打标记的时候还有冲突，要特别小心
上次写完了，查了半天没查出错来，于是放弃
今天对着标程打代码，终于抄完了，我已经不想再写了
const
maxn=;
type
node=record
data,sum,lc,rc,re,size,lmin,lmax,rmin,rmax:longint;
sw,inv:boolean;
end; var
f:array[..maxn]of node;
ans,root,n,m,i,x,y:longint;
ch:char; procedure swap(var x,y:longint);
var
t:longint;
begin
t:=x;x:=y;y:=t;
end; function min(x,y:longint):longint;
begin
if x<y then exit(x);
exit(y);
end; function max(x,y:longint):longint;
begin
if x>y then exit(x);
exit(y);
end; procedure updata(x:longint);
begin
with f[x] do
begin
size:=f[lc].size+f[rc].size+;
sum:=f[lc].sum+f[rc].sum+data;
lmax:=max(f[lc].lmax,f[lc].sum+data+f[rc].lmax);
lmin:=min(f[lc].lmin,f[lc].sum+data+f[rc].lmin);
rmax:=max(f[rc].rmax,f[rc].sum+data+f[lc].rmax);
rmin:=min(f[rc].rmin,f[rc].sum+data+f[lc].rmin);
end;
end; procedure release(x:longint);
begin
if x= then exit;
with f[x] do
begin
if re<> then
begin
data:=re;
sum:=size*re;
lmin:=min(,sum);
rmin:=lmin;
lmax:=max(,sum);
rmax:=lmax;
f[lc].re:=re;
f[rc].re:=re;
f[lc].inv:=false;
f[rc].inv:=false;
re:=;
end;
if sw then
begin
swap(lc,rc);
swap(lmax,rmax);
swap(lmin,rmin);
f[lc].sw:=not f[lc].sw;
f[rc].sw:=not f[rc].sw;
sw:=false;
end;
if inv then
begin
data:=-data;
sum:=-sum;
swap(lmin,lmax);
swap(rmin,rmax);
lmin:=-lmin;
lmax:=-lmax;
rmin:=-rmin;
rmax:=-rmax;
f[lc].inv:=not f[lc].inv;
f[rc].inv:=not f[rc].inv;
inv:=false;
end;
end;
end; procedure splay(x:longint;var root:longint);
var
tmp:longint;
begin
release(root);
release(f[root].lc);
release(f[root].rc);
if x=f[f[root].lc].size+ then exit;
if x<=f[f[root].lc].size then
begin
splay(x,f[root].lc);
tmp:=f[root].lc;
f[root].lc:=f[tmp].rc;
f[tmp].rc:=root;
updata(root);
root:=tmp;
end
else
begin
splay(x-f[f[root].lc].size-,f[root].rc);
tmp:=f[root].rc;
f[root].rc:=f[tmp].lc;
f[tmp].lc:=root;
updata(root);
root:=tmp;
end;
end; procedure splay(x:longint);
begin
splay(x,root);
updata(root);
end; procedure build(l,r:longint;var now:longint);
var
mid:longint;
begin
if l>r then exit;
mid:=(l+r)>>;
now:=mid;
build(l,mid-,f[mid].lc);
build(mid+,r,f[mid].rc);
updata(mid);
end; begin
readln(n,m);
for i:= to n+ do
begin
read(ch);
if ch='(' then f[i].data:=
else f[i].data:=-;
end;
build(,n+,root);
readln;
while m> do
begin
dec(m);
read(ch);
case ch of
'R':begin
readln(ch,ch,ch,ch,ch,ch,x,y,ch,ch);
splay(y+);
splay(x);
if ch='(' then f[f[f[root].rc].lc].re:=
else f[f[f[root].rc].lc].re:=-;
release(f[f[root].rc].lc);
updata(f[root].rc);
updata(root);
end;
'S':begin
readln(ch,ch,ch,x,y);
splay(y+);
splay(x);
f[f[f[root].rc].lc].sw:=true;
release(f[f[root].rc].lc);
updata(f[root].rc);
updata(root);
end;
'I':begin
readln(ch,ch,ch,ch,ch,x,y);
splay(y+);
splay(x);
f[f[f[root].rc].lc].inv:=true;
release(f[f[root].rc].lc);
updata(f[root].rc);
updata(root);
end;
'Q':begin
readln(ch,ch,ch,ch,x,y);
splay(y+);
splay(x);
writeln((-f[f[f[root].rc].lc].lmin)>>+(+f[f[f[root].rc].lc].rmax)>>);
end;
end;
end;
end.