题意(感谢@似水流年 翻译)

给你一个合法的括号序列,每次操作:

将一个位置的括号翻转,你要找到一个位置将这个括号也翻转,使得整个括号序列依旧合法;之后,你将这两个位置的括号翻转

*如果有多个解,找出编号最小的解

一个线段树的题..

我们把"("看成+1,")"看成-1

线段树维护前缀和

那么把"("改成")"就是找第一个")",改成"("

把")"改成"("...就麻烦了很多..

找到最后一个前缀和为1的地方,取它下一个位置

写了一次n log n的线段树

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<sstream>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
char a[300005];
set<int> l;
int val[1<<20];
int tag[1<<20];
void change(int num,int l,int r,int l0,int r0,int k)
{
    if ((l0<=l)&&(r<=r0))
    {
        val[num]+=k;
        tag[num]+=k;
        return;
    }
    int mid=(l+r)/2;
    if (l0<mid) change(num*2+1,l,mid,l0,r0,k);
    if (mid<r0) change(num*2+2,mid,r,l0,r0,k);
    val[num]=min(val[num*2+1],val[num*2+2])+tag[num];
}
int query(int num,int l,int r,int sum)
{
    if (val[num]+sum>=2) return -1;
    if (l==r-1)
    {
        return l;
    }
    int mid=(l+r)/2;
    sum+=tag[num];
    if (val[num*2+2]+sum>=2)
    {
        return query(num*2+1,l,mid,sum);
    }
    else
    {
        return query(num*2+2,mid,r,sum);
    }
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int n,q;
    scanf("%d%d",&n,&q);
    int i;
    scanf("%s",a);
    for (i=0;i<n;i++)
    {
        if (a[i]==')')
        {
            l.insert(i);
            change(0,0,n,i,n,-1);
        }
        else
        {
            change(0,0,n,i,n,1);
        }
    }
    for (i=0;i<q;i++)
    {
        int x;
        scanf("%d",&x);
        x--;
        if (a[x]==')')
        {
            a[x]='(';
            change(0,0,n,x,n,2);
            l.erase(x);
            int t=query(0,0,n,0);
            t++;
            printf("%d\n",t+1);
            a[t]=')';
            l.insert(t);
            change(0,0,n,t,n,-2);
        }
        else
        {
            a[x]=')';
            change(0,0,n,x,n,-2);
            l.insert(x);
            set<int>::iterator ii;
            ii=l.begin();
            a[(*ii)]='(';
            printf("%d\n",(*ii)+1);
            change(0,0,n,(*ii),n,2);
            l.erase(ii);
        }
    }
    return 0;
}