https://vjudge.net/contest/285175#problem/J
Main idea: give a string sss containing only "(" ("(" "(" and ")") "") "and make sure it is balanced (that is, the meaning of bracket matching). Then there are q q q queries. The third query flips s s [Q I] s [q] s [Qi] so that you can find the minimum subscript POS POS pos. After turning s[pos]s[pos]s[pos], the brackets of string sss are still balanced.

Idea: suppose that the value of "(" "(" is 111, ")") "") "is − 1-1 − 1, then we will change string sss into a sequence of numbers, and use line tree to maintain the prefix sum of this sequence. Take (()) ((()) (()) (()) for example, the values of each position are 1, 2, 3, 2, 1, 01, 2, 2, 1, 01, 2, 3, 2, 1, 0. Then consider the flipping operation. If s [Q I] = "(" s [q] = "(" s[qi] = "", flipping it is equivalent to subtracting 222 from the values of the interval [Qi, n] [Q, n] [Qi, n], otherwise it is equivalent to subtracting 222 from the values of the interval [Qi, n] [Q, n] [Qi, n] For the first operation, we need to find the first ') "") "") "and flip it. For the second operation, we need to find the most forward position POS pospospos from the back to the front to meet a [POS n]>=2a[pos… n]>=2a[pos… N]>=2. We introduce a value v[i]=a[i] − iv[i]=a[i]-iv[i]=a[i] − I. If v [i] < 0V [i] < 0V [i] < 0, it means that there are at least 111 ")" ")" in [1,i][1,i][1,i], so the answer of the first operation is the most forward position POS POS POS, which satisfies v [POS] < 0V [POS] < 0V [POS] < 0. Interval modification, interval query, use line tree, see the code for details.
tips:tips:tips: because of the particularity of the above operation interval, the modification of the interval in the query code is also very special. If you don't understand, you can look at the function call, and then think about it carefully.

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;

const int maxn=3e5+5;

struct Tree
{
    int l,r,m1,m2,lazy;
}tree[maxn<<2];

int n,q;
int a[maxn];
char s[maxn];

inline void up(int i)
{
    tree[i].m1=min(tree[i<<1].m1,tree[i<<1|1].m1);
    tree[i].m2=min(tree[i<<1].m2,tree[i<<1|1].m2);
}

inline void down(int i)
{
    int l=i<<1,r=i<<1|1,v=tree[i].lazy;
    tree[l].lazy+=v,tree[r].lazy+=v;
    tree[l].m1+=v,tree[r].m1+=v;
    tree[l].m2+=v,tree[r].m2+=v;
    tree[i].lazy=0;
}

void build(int i,int l,int r)
{
    tree[i].l=l,tree[i].r=r,tree[i].lazy=0;
    if(l==r)
    {
        tree[i].m1=a[l]-l;
        tree[i].m2=a[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(i<<1,l,mid);
    build(i<<1|1,mid+1,r);
    up(i);
}

void update(int i,int l,int r,int v)
{
    if(tree[i].l==l&&tree[i].r==r)
    {
        tree[i].m1+=v;
        tree[i].m2+=v;
        tree[i].lazy+=v;
        return ;
    }
    if(tree[i].lazy)
        down(i);
    int mid=(tree[i].l+tree[i].r)>>1;
    if(r<=mid)
        update(i<<1,l,r,v);
    else if(l>mid)
        update(i<<1|1,l,r,v);
    else
        update(i<<1,l,mid,v),update(i<<1|1,mid+1,r,v);
    up(i);
}

int query1(int i,int l,int r)//Find the left most M1 < 0 position in [l,r]
{
    if(l==r)
        return l;
    if(tree[i].lazy)
        down(i);
    int mid=(tree[i].l+tree[i].r)>>1;
    if(tree[i<<1].m1<0)
        return query1(i<<1,l,min(mid,r));
    else
        return query1(i<<1|1,mid+1,r);
}

int query2(int i,int l,int r)//Query the leftmost position pos in [l,r] to meet the requirement that m2 in [pos,r] is > = 2
{
    if(l==r) //l+1 is the place to satisfy the question~
        return l+1;
    if(tree[i].lazy)
        down(i);
    int mid=(tree[i].l+tree[i].r)>>1;
    if(tree[i<<1|1].m2>=2&&l<=mid)
        return query2(i<<1,l,mid);
    else
        return query2(i<<1|1,mid+1,r);
}

int main()
{
    scanf("%d%d",&n,&q);
    scanf("%s",s+1);
    for(int i=1;i<=n;i++)
    {
        if(s[i]=='(')
            a[i]=a[i-1]+1;
        else
            a[i]=a[i-1]-1;
    }
    build(1,1,n);
    int qi,id;
    while(q--)
    {
        scanf("%d",&qi);
        if(s[qi]=='(')
        {
            s[qi]=')',update(1,qi,n,-2);
            id=query1(1,1,qi);
            s[id]='(',update(1,id,n,2);
        }
        else
        {
            s[qi]='(',update(1,qi,n,2);
            id=query2(1,1,n);
            s[id]=')',update(1,id,n,-2);
        }
        printf("%d\n",id);
    }
    return 0;
}