题目链接

题意：有一个长度为 \(n\) 的括号序列，你需要支持以下操作：

基础的 fhq-treap 的题目，主要练下放标记的技巧。

首先我们需要将要求的东西转化为一个式子。例如括号序列 \((())))))((()\)，将左右括号抵消掉之后就是 \())))((\)，发现抵消完了之后变成了一段左括号跟一段右括号。

我们记 \((=-1\)，\()=1\)，假设前缀最大值为 \(mx\)，后缀最小值为 \(mn\)，那么最后会剩下 \(mx\) 个右括号和 \(-mn\) 个左括号，最少需要需要 \(\lceil \frac{mx}{2} \rceil+\lceil -\frac{mn}{2} \rceil\) 次操作。

我们建一棵平衡树，每个节点维护以下六个值：\(sz\) 子树大小，\(sum\) 子树权值和，\(prmn,prmx,sfmn,sfmx\) 表示前缀和后缀的最值，更新方式与最大子段和类似。

对于三个修改操作，我们考虑以下处理方式：

1. 区间赋值，直接维护标记然后更新 \(sum\) 和 最值。
2. 区间翻转操作，直接交换左右儿子和前、后缀最大最小值。
3. 区间取逆操作，实际上就是将每个点的权值变为它的相反数，它的和、前后缀最大最小值也都变为了各自的相反数，如果有赋值标记，那么赋值标记也要取反。需要注意的一点是，最大值取了个相反数之后就变成了最小值，最小值取了相反数之后就变成了最大值，因此还需 swap 一下。

细节还是挺多的，代码也调了不少时间：

//Coded by tzc_wk
/*
数据不清空，爆零两行泪。
多测不读完，爆零两行泪。
边界不特判，爆零两行泪。
贪心不证明，爆零两行泪。
D P 顺序错，爆零两行泪。
大小少等号，爆零两行泪。
变量不统一，爆零两行泪。
越界不判断，爆零两行泪。
调试不注释，爆零两行泪。
溢出不 l l，爆零两行泪。
*/
#include <bits/stdc++.h>
using namespace std;
#define fi            first
#define se            second
#define fz(i,a,b)    for(int i=a;i<=b;i++)
#define fd(i,a,b)    for(int i=a;i>=b;i--)
#define foreach(it,v) for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define all(a)        a.begin(),a.end()
#define giveup(...) return printf(__VA_ARGS__),0;
#define fill0(a)    memset(a,0,sizeof(a))
#define fill1(a)    memset(a,-1,sizeof(a))
#define fillbig(a)    memset(a,0x3f,sizeof(a))
#define fillsmall(a) memset(a,0xcf,sizeof(a))
#define mask(a)        (1ll<<(a))
#define maskx(a,x)    ((a)<<(x))
#define _bit(a,x)    (((a)>>(x))&1)
#define _sz(a)        ((int)(a).size())
#define filei(a)    freopen(a,"r",stdin);
#define fileo(a)    freopen(a,"w",stdout);
#define fileio(a)     freopen(a".in","r",stdin);freopen(a".out","w",stdout)
#define eprintf(...) fprintf(stderr,__VA_ARGS__)
#define put(x)        putchar(x)
#define eoln        put('\n')
#define space        put(' ')
#define y1            y_chenxiaoyan_1
#define y0            y_chenxiaoyan_0
typedef pair<int,int> pii;
inline int read(){
    int x=0,neg=1;char c=getchar();
    while(!isdigit(c)){
        if(c=='-')  neg=-1;
        c=getchar();
    }
    while(isdigit(c))   x=x*10+c-'0',c=getchar();
    return x*neg;
}
inline void print(int x){
    if(x<0){
        putchar('-');
        print(abs(x));
        return;
    }
    if(x<=9)    putchar(x+'0');
    else{
        print(x/10);
        putchar(x%10+'0');
    }
}
inline int qpow(int x,int e,int _MOD){
    int ans=1;
    while(e){
        if(e&1) ans=ans*x%_MOD;
        x=x*x%_MOD;
        e>>=1;
    }
    return ans;
}
int n=read(),m=read();
char str[100005];
struct node{
    int ch[2],val,key;
    int prmx,prmn,sfmx,sfmn,sum,sz;
    int rv_lz,cov_lz,inv_lz;
} s[100005];
int ncnt=0,root;
inline void pushup(int k){
//    s[0].prmx=s[0].sfmx=0;s[0].prmn=s[0].sfmn=0x3f3f3f3f;
    s[k].prmx=max(s[s[k].ch[0]].prmx,s[s[k].ch[0]].sum+s[k].val+s[s[k].ch[1]].prmx);
    s[k].prmn=min(s[s[k].ch[0]].prmn,s[s[k].ch[0]].sum+s[k].val+s[s[k].ch[1]].prmn);
    s[k].sfmx=max(s[s[k].ch[1]].sfmx,s[s[k].ch[1]].sum+s[k].val+s[s[k].ch[0]].sfmx);
    s[k].sfmn=min(s[s[k].ch[1]].sfmn,s[s[k].ch[1]].sum+s[k].val+s[s[k].ch[0]].sfmn);
    s[k].sum=s[s[k].ch[0]].sum+s[s[k].ch[1]].sum+s[k].val;
    s[k].sz=s[s[k].ch[0]].sz+s[s[k].ch[1]].sz+1;
}
inline void inv_part(int k){
    s[k].val=-s[k].val;s[k].sum=-s[k].sum;
    int prmn=s[k].prmn,prmx=s[k].prmx,sfmn=s[k].sfmn,sfmx=s[k].sfmx;
    s[k].prmn=-prmx;s[k].prmx=-prmn;s[k].sfmn=-sfmx;s[k].sfmx=-sfmn;
    s[k].cov_lz=-s[k].cov_lz;
    s[k].inv_lz^=1;
}
inline void cov_part(int k,int mk){
    s[k].val=mk;
    s[k].sum=mk*s[k].sz;
    s[k].cov_lz=mk;
    if(mk==1){s[k].prmn=s[k].sfmn=0;s[k].prmx=s[k].sfmx=s[k].sum;}
    else{s[k].prmx=s[k].sfmx=0;s[k].prmn=s[k].sfmn=s[k].sum;}
}
inline void rev_part(int k){
    swap(s[k].ch[0],s[k].ch[1]);
    swap(s[k].prmn,s[k].sfmn);
    swap(s[k].prmx,s[k].sfmx);
    s[k].rv_lz^=1;
}
inline void pushdown(int k){
    if(s[k].inv_lz){
        if(s[k].ch[0])  inv_part(s[k].ch[0]);
        if(s[k].ch[1])  inv_part(s[k].ch[1]);
        s[k].inv_lz=0;
    }
    if(s[k].cov_lz){
        if(s[k].ch[0])  cov_part(s[k].ch[0],s[k].cov_lz);
        if(s[k].ch[1])  cov_part(s[k].ch[1],s[k].cov_lz);
        s[k].cov_lz=0;
    }
    if(s[k].rv_lz){
        if(s[k].ch[0])  rev_part(s[k].ch[0]);
        if(s[k].ch[1])  rev_part(s[k].ch[1]);
        s[k].rv_lz=0;
    }
}
inline int newnode(char c){
    ncnt++;
    s[ncnt].key=rand()<<15|rand();
    s[ncnt].sz=1;
    if(c=='('){
        s[ncnt].prmn=s[ncnt].sfmn=-1;
        s[ncnt].prmx=s[ncnt].sfmx=0;
        s[ncnt].sum=-1;
        s[ncnt].val=-1;
    }
    else{
        s[ncnt].prmn=s[ncnt].sfmn=0;
        s[ncnt].prmx=s[ncnt].sfmx=1;
        s[ncnt].sum=1;
        s[ncnt].val=1;
    }
    return ncnt;
}
inline void build(int &k,int l,int r){
    int mid=(l+r)>>1;
    k=newnode(str[mid]);
    if(l!=mid)  build(s[k].ch[0],l,mid-1);
    if(r!=mid)  build(s[k].ch[1],mid+1,r);
    pushup(k);
}
inline void split(int k,int sz,int &a,int &b){
    if(!k){
        a=b=0;
        return;
    }
    pushdown(k);
    if(sz<=s[s[k].ch[0]].sz){
        b=k;
        split(s[k].ch[0],sz,a,s[k].ch[0]);
    }
    else{
        a=k;
        split(s[k].ch[1],sz-s[s[k].ch[0]].sz-1,s[k].ch[1],b);
    }
    pushup(k);
}
inline int merge(int a,int b){
    pushdown(a);pushdown(b);
    if(!a||!b)  return a+b;
    if(s[a].key<s[b].key){
        s[a].ch[1]=merge(s[a].ch[1],b);
        pushup(a);return a;
    }
    else{
        s[b].ch[0]=merge(a,s[b].ch[0]);
        pushup(b);return b;
    }
}
inline void rev(int l,int r){
    int k1,k2,k3;
    split(root,l-1,k1,k2);
    split(k2,r-l+1,k2,k3);
    rev_part(k2);
    root=merge(merge(k1,k2),k3);
}
inline void inv(int l,int r){
    int k1,k2,k3;
    split(root,l-1,k1,k2);
    split(k2,r-l+1,k2,k3);
    inv_part(k2);
    root=merge(merge(k1,k2),k3);
}
inline void cov(int l,int r,int x){
    int k1,k2,k3;
    split(root,l-1,k1,k2);
    split(k2,r-l+1,k2,k3);
    cov_part(k2,x);
    root=merge(merge(k1,k2),k3);
}
inline int getf(int x){
    if(x&1) return (x>>1)+1;
    else    return x>>1;
}
inline int query(int l,int r){
    int k1,k2,k3;
    split(root,l-1,k1,k2);
    split(k2,r-l+1,k2,k3);
    int res=getf(s[k2].prmx)+getf(abs(s[k2].sfmn));
    root=merge(merge(k1,k2),k3);
    return res;
}
signed main(){
    cin>>str+1;
    build(root,1,n);
    while(m--){
        char opt[10];cin>>opt+1;
        if(opt[1]=='R'){
            int l=read(),r=read();
            char c;cin>>c;
            if(c=='(')  cov(l,r,-1);
            else        cov(l,r,1);
        }
        if(opt[1]=='S'){
            int l=read(),r=read();
            rev(l,r);
        }
        if(opt[1]=='I'){
            int l=read(),r=read();
            inv(l,r);
        }
        if(opt[1]=='Q'){
            int l=read(),r=read();
            cout<<query(l,r)<<endl;
        }

    }
    return 0;
}