Link
Description
给定一个括号序列 (S)，需要支持 4 种操作。
- 区间覆盖
- 翻转区间
- 翻转区间内的括号
- 询问某区间需要翻转多少括号后使得其合法
Solution
看到区间翻转就容易想到平衡树了。
主要是处理询问。我们知道括号匹配后一定长 ')))(((' 这种样子，需要改变的括号数就是 (lceil frac{左括号个数+1}{2} ceil+lceil frac{右括号个数+1}{2} ceil) 。但直接维护括号个数不好处理，因为有翻转操作。注意到一个不显然的性质，把 '(' 看成 1 ')' 看成 -1，那么左括号个数就是区间最大前缀和，右括号个数就是区间最小后缀和。所以我们可以考虑维护这两个东西。
翻转区间会把前缀变后缀，后缀变前缀。其实就是交换前后缀信息。所以还要同时维护一个前缀最小和后缀最大。
翻转括号相当于交换了符号，那么原来的最大值就是现在的最小值。所以交换最大最小值，并取反即可。
最后注意一下要维护三个对应的 tag ，且操作之中有覆盖关系。即区间覆盖会直接使之前的翻转操作失效。所以打覆盖 tag 的时候，要记得清空另外两个 tag。
又由于是平衡树维护，实际上每个点即代表一段区间又代表它本身的那个位置。所以修改区间的时候要记得同时更新位置的信息。
#include<stdio.h>
#include<stdlib.h>
#define Ls(id) t[id].Ls
#define Rs(id) t[id].Rs
#define Tag(id) (t[id].Inv||t[id].swp||t[id].cv)
inline int read(){
int x=0,flag=1; char c=getchar();
while(c<'0'||c>'9'){if(c=='-') flag=0;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-48;c=getchar();}
return flag? x:-x;
}
const int N=1e5+7;
struct Node{
int Ls,Rs,sz,key,val;
int lmax,lmin,rmax,rmin,s;
int Inv,swp,cv;
}t[N];
inline void swap(int &x,int &y){x^=y,y^=x,x^=y;}
inline int max(int x,int y){return x>y? x:y;}
inline int min(int x,int y){return x<y? x:y;}
inline int New(int val){
static int tot=0;
t[++tot]=(Node){0,0,1,rand()*rand(),val,0,0,0,0,val,0,0};
if(~val) t[tot].lmax=t[tot].rmax=1;
else t[tot].lmin=t[tot].rmin=-1;
return tot;
}
inline void update(int id){
t[id].s=t[Ls(id)].s+t[Rs(id)].s+t[id].val;
t[id].sz=t[Ls(id)].sz+t[Rs(id)].sz+1;
t[id].lmax=max(t[Ls(id)].lmax,t[Ls(id)].s+t[id].val+t[Rs(id)].lmax);
t[id].lmin=min(t[Ls(id)].lmin,t[Ls(id)].s+t[id].val+t[Rs(id)].lmin);
t[id].rmax=max(t[Rs(id)].rmax,t[Rs(id)].s+t[id].val+t[Ls(id)].rmax);
t[id].rmin=min(t[Rs(id)].rmin,t[Rs(id)].s+t[id].val+t[Ls(id)].rmin);
}
inline void Cv(int id,int c){
t[id].swp=t[id].Inv=0;
t[id].val=t[id].cv=c;
t[id].s=c*t[id].sz;
if(~c){
t[id].lmax=t[id].rmax=t[id].sz;
t[id].lmin=t[id].rmin=0;
}else{
t[id].lmax=t[id].rmax=0;
t[id].lmin=t[id].rmin=-t[id].sz;
}
}
inline void Swp(int id){
swap(Ls(id),Rs(id));
swap(t[id].lmax,t[id].rmax);
swap(t[id].lmin,t[id].rmin);
t[id].swp^=1;
}
inline void Inv(int id){
t[id].Inv^=1;
t[id].val*=-1,t[id].s*=-1;
swap(t[id].lmax,t[id].lmin);
t[id].lmax*=-1,t[id].lmin*=-1;
swap(t[id].rmax,t[id].rmin);
t[id].rmax*=-1,t[id].rmin*=-1;
}
inline void pd(int id){
if(t[id].cv){
Cv(Ls(id),t[id].cv);
Cv(Rs(id),t[id].cv);
t[id].cv=0;
}
if(t[id].swp){
Swp(Ls(id)),Swp(Rs(id));
t[id].swp=0;
}
if(t[id].Inv){
Inv(Ls(id)),Inv(Rs(id));
t[id].Inv=0;
}
}
int merge(int x,int y){
if(!x||!y) return x+y;
if(t[x].key<t[y].key){
if(Tag(x)) pd(x);
Rs(x)=merge(Rs(x),y);
return update(x),x;
}else{
if(Tag(y)) pd(y);
Ls(y)=merge(x,Ls(y));
return update(y),y;
}
}
void split(int id,int k,int &x,int &y){
if(!id) x=y=0;
else{
if(Tag(id)) pd(id);
if(t[Ls(id)].sz+1<=k)
x=id,split(Rs(id),k-t[Ls(id)].sz-1,Rs(id),y);
else y=id,split(Ls(id),k,x,Ls(id));
update(id);
}
}
char s[N],opt[10];
int main(){
srand(114514);
int n=read(),m=read(),rt=0;
scanf("%s",s+1);
for(int i=1;i<=n;i++)
rt=merge(rt,New(s[i]=='('? 1:-1));
int x,y,z,l,r;
while(m--){
scanf("%s",opt);
l=read(),r=read();
split(rt,r,y,z),split(y,l-1,x,y);
if(opt[0]=='R'){
scanf("%s",opt);
Cv(y,opt[0]=='('? 1:-1);
}else if(opt[0]=='S') Swp(y);
else if(opt[0]=='I') Inv(y);
else printf("%d
",(-t[y].lmin+1)/2+(t[y].rmax+1)/2);
rt=merge(merge(x,y),z);
}
}