【hdu 5217】Brackets

Description

Miceren likes playing with brackets.

There are N brackets on his desk forming a sequence. In his spare time, he will do Q operations on this sequence, each operation is either of these two types:

1. Flip the X-th bracket, i.e. the X-th bracket will become ) if it is ( before, otherwise become ( .

2. In a given subsequence [L, R], query the K-th bracket position number after deleting all matched brackets. If the amount of brackets left is less than K, output -1. For example, if N = 10, L = 2, R = 9 and the sequence is ))(()))((). In the sub sequence [2, 9], the brackets sequence is )(()))((. After deleting all matched brackets, the sequence becomes ) )((. If K = 1, answer is 2. If K = 2, answer is 7. If K = 3, answer is 8. If K = 4, answer is 9. If K ≥ 5, answer is -1.

Miceren is good at playing brackets, instead of calculating them by himself.

As his friend, can you help him?

Input

The first line contains a single integer T, indicating the number of test cases.

Each test case begins with two integers N, Q, indicating the number of brackets in Miceren's desk and the number of queries.

Each of following Q lines describes an operation: if it is "1 X", it indicate the first type of operation. Otherwise it will be "2 L R K", indicating the second type of operation.

T is about 100.

1 ≤ N,Q ≤ 200000.

For each query, 1 ≤ X ≤ N and 1 ≤ L ≤ R ≤ N, 1 ≤ K ≤ N.

The ratio of test cases with N > 100000 is less than 10%.

Output

For each query operation, output the answer. If there is no K brackets left, output -1.

Sample Input

10 5

))(()))(()

2 2 9 2

2 2 9 3

2 2 9 5

1 3

2 2 9 5

Sample Output

-1

题意：给出一个括号序列和2种操作：1.翻转某一个括号；2.查询区间内完成括号匹配后第k个括号的原位置。（$1\leq N,Q \leq 200000$）

分析：

易得，最后的序列一定形如 ')))(((' ，即左段皆为 ')'，右段皆为 '(' 。我们可以建出一棵线段树，线段树上的每个节点对应区间内匹配后左段 '(' 的数量和右段 ')' 的数量。

区间合并与修改显然，主要问题在查询。至此我们可以通过查询区间[L,R]的信息快速得到第k个括号的类型。因为 '(' 在从右往左合并区间时单调不减， ')' 在从左往右合并区间时单调不减，所以可以在线段树上边跑边查询。详见代码。

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #define lc x<<1

 #define rc x<<1|1

 #define LL long long

 using namespace std;

 const int N=5e5+;

 int T,n,m,op,L,R,x;

 int a[N],id[N],tl[N*],tr[N*];

 char ch[N];

 struct node{int t1,t0;}ans,now,tmp,t[N*];

 int read()

 {

     int x=,f=;char c=getchar();

     while(c<''||c>''){if(c=='-')f=-;c=getchar();}

     while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

     return x*f;

 }

 node merge(node a,node b)

 {

     node c=(node){a.t1,b.t0};

     if(a.t0>b.t1)c.t0+=a.t0-b.t1;

     else c.t1+=b.t1-a.t0;

     return c;

 }

 void build(int x,int l,int r)

 {

     tl[x]=l;tr[x]=r;

     if(l==r)

     {

         if(a[l])t[x]=(node){,};

         else t[x]=(node){,};

         id[l]=x;return;

     }

     int mid=(l+r)>>;

     build(lc,l,mid);

     build(rc,mid+,r);

     t[x]=merge(t[lc],t[rc]);

 }

 void modify(int x,int l,int r,int p)

 {

     if(l==r)

     {

         swap(t[x].t0,t[x].t1);

         return;

     }

     int mid=(l+r)>>;

     if(p<=mid)modify(lc,l,mid,p);

     else modify(rc,mid+,r,p);

     t[x]=merge(t[lc],t[rc]);

 }

 void query(int x,int l,int r)

 {

     if(L<=l&&r<=R)

     {

         ans=merge(ans,t[x]);

         return;

     }

     int mid=(l+r)>>;

     if(L<=mid)query(lc,l,mid);

     if(R>mid)query(rc,mid+,r);

 }

 int work0(int x,int l,int r,int goal)

 {

     if(l==r)return l;

     int mid=(l+r)>>;

     tmp=now;now=merge(t[rc],now);

     if(now.t0>=goal)

     {

         now=tmp;

         return work0(rc,mid+,r,goal);

     }

     return work0(lc,l,mid,goal);

 }

 int find0(int p,int goal)

 {

     int x=id[p];

     bool flag=false;

     now=merge(t[x],now);

     if(now.t0==goal)return p;

     if(x&)flag=true;

     while()

     {

         x>>=;

         if(flag)

         {

             tmp=now;now=merge(t[lc],now);

             if(now.t0>=goal){now=tmp;x=lc;break;}

         }

         if(x&)flag=true;

         else flag=false;

     }

     return work0(x,tl[x],tr[x],goal);

 }

 int work1(int x,int l,int r,int goal)

 {

     if(l==r)return l;

     int mid=(l+r)>>;

     tmp=now;now=merge(now,t[lc]);

     if(now.t1>=goal)

     {

         now=tmp;

         return work1(lc,l,mid,goal);

     }

     return work1(rc,mid+,r,goal);

 }

 int find1(int p,int goal)

 {

     int x=id[p];

     bool flag=true;

     now=merge(now,t[x]);

     if(now.t1==goal)return p;

     if(x&)flag=false;

     while()

     {

         x>>=;

         if(flag)

         {

             tmp=now;now=merge(now,t[rc]);

             if(now.t1>=goal){now=tmp;x=rc;break;}

         }

         if(x&)flag=false;

         else flag=true;

     }

     return work1(x,tl[x],tr[x],goal);

 }

 void work()

 {

     n=read();m=read();

     scanf("%s",ch+);

     for(int i=;i<=n;i++)

         if(ch[i]=='(')a[i]=;

         else a[i]=;

     build(,,n);

     while(m--)

     {

         op=read();

         if(op==)

         {

             x=read();

             modify(,,n,x);

             continue;

         }

         L=read();R=read();x=read();

         ans.t0=ans.t1=;

         query(,,n);

         if(ans.t0+ans.t1<x)

         {

             printf("-1\n");

             continue;

         }

         now.t0=now.t1=;

         if(x<=ans.t1)printf("%d\n",find1(L,x));

         else printf("%d\n",find0(R,ans.t0+ans.t1-x+));

     }

 }

 int main()

 {

     T=read();

     while(T--)work();

     return ;

 }

巴特西