题意：给一串括号，有2个操作，1。翻转某个括号。2。查询某段区间内化简后第k个括号是在原序列中的位置。1 ≤ N,Q ≤ 200000.

题解：

可以知道，化简后的序列一定是)))((((这种形式的。

线段树每个节点就存对应区间内化简后的ls也就是)的数量，rs也就是(的数量。

然后我先把区间[l,r]找出来合并一遍，找出第k个是哪一种扩号。

问题转化为找区间[l,r]中的第kk个左扩号或者右括号。

我们可以发现，如果是)这种括号，区间从左到右合并的时候是单调不减的。

同理，(这种括号，区间从右往左合并的时候也是单调不减的。

然后我是变成从左往右的第kk个），或者从右往左的第kk个（。

[l,r]这个区间在线段树里可能由若干个区间组合而来，我们就根据左右括号的不同从左或从右合一遍，恰好遇到第kk个的时候就进去找。这个找就简单很多，因为它就是在线段树上走一遍的。

细节挺多的。

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 using namespace std;  7   8 const int N=200010;  9 int n,m,tl,cl,c[N]; 10 char s[N]; 11 struct node{ 12     int l,r,lc,rc,ls,rs;// ls ))) rs ((( 13 }t[2*N]; 14  15 int maxx(int x,int y){
    return x>y ? x:y;} 16  17 node upd(node x,node lc,node rc) 18 { 19     x.ls=lc.ls; 20     x.rs=rc.rs; 21     int sum=rc.ls-lc.rs; 22     if(sum>0) x.ls+=sum; 23     else x.rs+=-sum; 24     // x.ls=maxx(0,lc.ls+rc.ls-lc.rs); 25     // x.rs=maxx(0,rc.rs+lc.rs-rc.ls); 26     return x; 27 } 28  29 int bt(int l,int r) 30 { 31     int x=++tl; 32     t[x].l=l;t[x].r=r; 33     t[x].lc=t[x].rc=0; 34     t[x].ls=t[x].rs=0; 35     if(l
          
           mid) query(rc,l,r); 66 else 67 { 68 query(lc,l,mid); 69 query(rc,mid+1,r); 70 } 71 } 72 73 int fd(int x,int k,int tmp) 74 { 75 if(t[x].l==t[x].r) return t[x].l; 76 int lc=t[x].lc,rc=t[x].rc; 77 if(tmp==0) 78 { 79 if(t[lc].ls>=k) return fd(lc,k,tmp); 80 return fd(rc,k-t[lc].ls+t[lc].rs,tmp); 81 } 82 else 83 { 84 if(t[rc].rs>=k) return fd(rc,k,tmp); 85 return fd(lc,k-t[rc].rs+t[rc].ls,tmp); 86 } 87 } 88 89 int main() 90 { 91 freopen("a.in","r",stdin); 92 freopen("a.out","w",stdout); 93 int T; 94 scanf("%d",&T); 95 while(T--) 96 { 97 scanf("%d%d",&n,&m); 98 scanf("%s",s+1); 99 tl=0;bt(1,n);100 for(int i=1;i<=m;i++)101 {102 int tmp,x,l,r,k,ans;103 scanf("%d",&tmp);104 if(tmp==1)105 {106 scanf("%d",&x);107 change(1,x);108 }109 else 110 {111 scanf("%d%d%d",&l,&r,&k);112 cl=0;query(1,l,r);113 node now=t[c[1]];114 for(int j=2;j<=cl;j++) now=upd(now,now,t[c[j]]);115 if(now.ls+now.rs
           
            =k) 117 {118 node p0=t[c[1]],p1;119 if(p0.ls>=k) ans=fd(c[1],k,0);120 else121 {122 for(int j=2;j<=cl;j++)123 {124 p1=upd(p1,p0,t[c[j]]);125 if(p1.ls>=k) 126 {127 ans=fd(c[j],k-p0.ls+p0.rs,0);128 break;129 }130 p0=p1;131 }132 }133 }134 else 135 {136 k=now.ls+now.rs-k+1;137 node p0=t[c[cl]],p1;138 if(p0.rs>=k) ans=fd(c[cl],k,1);139 else140 {141 for(int j=cl-1;j>=1;j--)142 {143 p1=upd(p1,t[c[j]],p0);144 if(p1.rs>=k) {ans=fd(c[j],k-p0.rs+p0.ls,1);break;}145 p0=p1;146 }147 }148 }149 printf("%d\n",ans);150 }151 }152 }153 return 0;154 }