1 #include<cstdio>  2 #include<cstdlib>  3 #include<cmath>  4 #include<cstring>  5 #include<algorithm>  6 #include<iostream>  7 #include<vector>  8 #include<map>  9 #include<set> 10 #include<queue> 11 #include<string> 12 #define inf 1000000000 13 #define maxn 150000+5 14 #define maxm 500+100 15 #define eps 1e-10 16 #define ll long long 17 #define pa pair<int,int> 18 #define for0(i,n) for(int i=0;i<=(n);i++) 19 #define for1(i,n) for(int i=1;i<=(n);i++) 20 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 21 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 22 #define mod 1000000007 23 using namespace std; 24 inline int read() 25 { 26     int x=0,f=1;char ch=getchar(); 27     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 28     while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 29     return x*f; 30 } 31 int n,m,c[maxn][2],fa[maxn],li[maxn],ri[maxn],lx[maxn],rx[maxn],sum[maxn],s[maxn],v[maxn]; 32 int rt,t1,t2; 33 bool cov[maxn],rev[maxn],inv[maxn]; 34 inline void pushup(int x) 35 { 36     int l=c[x][0],r=c[x][1]; 37     s[x]=s[l]+s[r]+1; 38     sum[x]=sum[l]+sum[r]+v[x]; 39     lx[x]=max(lx[l],sum[l]+v[x]+max(0,max(lx[r],sum[r]))); 40     rx[x]=max(rx[r],sum[r]+v[x]+max(0,max(rx[l],sum[l]))); 41     li[x]=min(li[l],sum[l]+v[x]+min(0,min(li[r],sum[r]))); 42     ri[x]=min(ri[r],sum[r]+v[x]+min(0,min(ri[l],sum[l]))); 43 } 44 inline void rotate(int x,int &k) 45 { 46     int y=fa[x],z=fa[y],l=c[y][1]==x,r=l^1; 47     if(y!=k)c[z][c[z][1]==y]=x;else k=x; 48     fa[x]=z;fa[y]=x;fa[c[x][r]]=y; 49     c[y][l]=c[x][r];c[x][r]=y; 50     pushup(y);pushup(x); 51 } 52 inline void splay(int x,int &k) 53 { 54     while(x!=k) 55     { 56         int y=fa[x],z=fa[y]; 57         if(y!=k) 58         { 59             if(c[z][0]==y^c[y][0]==x)rotate(x,k);else rotate(y,k); 60         } 61         rotate(x,k); 62     } 63 } 64 inline void cover(int x,int y) 65 { 66     cov[x]=1;v[x]=y;rev[x]=inv[x]=0; 67     sum[x]=s[x]*y; 68     lx[x]=rx[x]=y>0?sum[x]:0; 69     li[x]=ri[x]=y>0?0:sum[x]; 70 } 71 inline void rever(int x) 72 { 73     if(cov[x])return; 74     rev[x]^=1; 75     swap(c[x][0],c[x][1]); 76     swap(lx[x],rx[x]); 77     swap(li[x],ri[x]); 78 } 79 inline void invert(int x) 80 { 81     inv[x]^=1;v[x]=-v[x]; 82     swap(li[x],lx[x]);li[x]=-li[x];lx[x]=-lx[x]; 83     swap(ri[x],rx[x]);ri[x]=-ri[x];rx[x]=-rx[x]; 84     sum[x]=-sum[x]; 85     if(cov[x])inv[x]=0; 86 } 87 inline void pushdown(int x) 88 { 89     if(cov[x]){cover(c[x][0],v[x]);cover(c[x][1],v[x]);cov[x]=0;} 90     if(rev[x]){rever(c[x][0]);rever(c[x][1]);rev[x]=0;} 91     if(inv[x]){invert(c[x][0]);invert(c[x][1]);inv[x]=0;} 92 } 93 inline int find(int x,int k) 94 { 95     pushdown(x); 96     int l=c[x][0],r=c[x][1]; 97     if(s[l]+1==k)return x; 98     else if(s[l]>=k)return find(l,k); 99     else return find(r,k-s[l]-1);100 }101 inline void split(int l,int r)102 {103     t1=find(rt,l);t2=find(rt,r);104     splay(t1,rt);splay(t2,c[t1][1]);105 }106 inline void build(int l,int r,int f)107 {108     if(l>r)return;109     int x=(l+r)>>1;110     fa[x]=f;c[f][x>f]=x;111     if(l==r){s[x]=1;li[x]=ri[x]=v[x]>0?0:v[x];lx[x]=rx[x]=v[x]>0?v[x]:0;sum[x]=v[x];return;}112     build(l,x-1,x);build(x+1,r,x);113     pushup(x);114 }115 int main()116 {117     freopen("input.txt","r",stdin);118     freopen("output.txt","w",stdout);119     n=read();m=read();120     v[1]=v[n+2]=0;121     for2(i,2,n+1){char ch=getchar();while(ch!=‘(‘&&ch!=‘)‘)ch=getchar();v[i]=ch==‘(‘?1:-1;}122     build(1,n+2,0);rt=(1+n+2)>>1;123     while(m--)124     {125         int ch=read();int x=read(),y=read();split(x,y+2);int z=c[t2][0];126         if(!ch)printf("%d\n",(-li[z]+1)/2+(rx[z]+1)/2);127         else if(ch==1)invert(z);else rever(z);128         pushup(t2);pushup(t1);129     }130     return 0;131 }