自动搬运

查看原文

来自洛谷，原作者为

	Wf_yjqd 哀酱永远的神/tyt /se /qq!!!

搬运于2025-08-24 22:42:14，当前版本为作者最后更新于2023-06-02 21:09:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

比较基础的线段树板子。

若用 $1$ 表示左括号，$-1$ 表示右括号，求原串的前缀和 $sum_i$，考虑 $[l,r]$ 为合法括号序列的条件:

1.$sum_{l-1}=sum_r$。

2.对于任意 $i$ 满足 $l\le i\le r$，有 $sum_{l-1}\le sum_i$。

考虑式二可以用区间最小值维护，且满足单调性，于是想到线段树 $+$ 二分。

满足式二以后，只要找到解集中最右一个满足式一的即可。

如果 $sum_{l-1}\le sum_i<sum_{l-1}+1$ 且 $sum_i\in\mathbb{Z}$，则 $sum_{l-1}=sum_i$。

因此式一也满足单调性，这样先在 $x$ 向右二分式二，再在式二最大取值向左二分式一，就可以处理询问了。

那么，如何处理修改操作呢？

考虑如果要把一个区间 $[l,r]$ 取反，完全可以分成 $[1,l-1]$ 和 $[1,r]$ 分别取反。

这样就可以分成两个左端点为 $1$ 的区间，于是可以用上面的前缀和维护了。

具体来说，将 $[1,x]$ 取反的代价为：

$sum_i(1\le i\le x)$ 全取相反数，$sum_i(x+1\le i\le n)$ 全加上 $-sum_x\times 2$。

前者影响了最小值，所以再维护一个最大值，每次先交换最大和最小值再取反。

后者中，单点查询 $sum_x$，然后用懒惰标记处理区间加就行。

总体复杂度 $\operatorname{O}(m\times\log n)$。

码量还行吧（可能线段树本身长），基本就板子。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+84;
const int maxt=5e6+84;
int n,m,op,x,y,ans,slast,qzh[maxn];
char s[maxn];
struct Point{
    int l,r,miin,maax,lazy_swap,lazy_add;
};
struct Tree{
    Point T[maxt];
    inline void pushup(int x){
        T[x].maax=max(T[x<<1].maax,T[x<<1|1].maax);
        T[x].miin=min(T[x<<1].miin,T[x<<1|1].miin);
        return ;
    }
    inline void swp(int x){
        swap(T[x].maax,T[x].miin);
        T[x].maax*=-1;
        T[x].miin*=-1;
        T[x].lazy_add*=-1;
        T[x].lazy_swap^=1;
        return ;
    }
    inline void addd(int x,int val){
        T[x].miin+=val;
        T[x].maax+=val;
        T[x].lazy_add+=val;
        return ;
    }
    inline void pushdown(int x){
        if(T[x].lazy_swap){
            swp(x<<1);
            swp(x<<1|1);
            T[x].lazy_swap=0;
        }
        if(T[x].lazy_add){
            addd(x<<1,T[x].lazy_add);
            addd(x<<1|1,T[x].lazy_add);
            T[x].lazy_add=0;
        }
        return ;
    }
    inline void init(int id,int l,int r){
        T[id].l=l;
        T[id].r=r;
        if(l==r){
            T[id].maax=T[id].miin=qzh[l];
            return ;
        }
        int mid=l+r>>1;
        init(id<<1,l,mid);
        init(id<<1|1,mid+1,r);
        pushup(id);
        return ;
    }
    inline void add(int id,int l,int r,int val){
        if(l<=T[id].l&&T[id].r<=r){
            addd(id,val);
            return ;
        }
        pushdown(id);
        int mid=T[id].l+T[id].r>>1;
        if(l<=mid)
            add(id<<1,l,r,val);
        if(mid<r)
            add(id<<1|1,l,r,val);
        pushup(id);
        return ;
    }
    inline void swapp(int id,int l,int r){
        if(l<=T[id].l&&T[id].r<=r){
            swp(id);
            return ;
        }
        pushdown(id);
        int mid=T[id].l+T[id].r>>1;
        if(l<=mid)
            swapp(id<<1,l,r);
        if(mid<r)
            swapp(id<<1|1,l,r);
        pushup(id);
        return ;
    }
    inline int query_p(int id,int pos){
        if(!pos)
            return 0;
        if(T[id].l==T[id].r)
            return T[id].maax;
        pushdown(id);
        int mid=T[id].l+T[id].r>>1;
        if(pos<=mid)
            return query_p(id<<1,pos);
        return query_p(id<<1|1,pos);
    }
    inline void modify(int x){
        if(!x)
            return ;
        if(x<n)
            add(1,x+1,n,-query_p(1,x)*2);
        swapp(1,1,x);
        return ;
    }
    inline int bsy(int id,int x,int val){
        if(T[id].l==T[id].r)
            return T[id].l;
        pushdown(id);
        int anss=n+1,mid=T[id].l+T[id].r>>1;
        if(T[id<<1].miin<val&&x<=mid)
            anss=bsy(id<<1,x,val);
        if(anss!=n+1)
            return anss;
        if(T[id<<1|1].miin<val)
            anss=bsy(id<<1|1,x,val);
        return anss;
    }
    inline int bsz(int id,int x,int val){
        if(T[id].l==T[id].r)
            return T[id].l;
        pushdown(id);
        int anss=-168,mid=T[id].l+T[id].r>>1;
        if(T[id<<1|1].miin<val&&x>mid)
            anss=bsz(id<<1|1,x,val);
        if(anss>0)
            return anss;
        if(T[id].miin<val)
            anss=bsz(id<<1,x,val);
        return anss;
    }
    inline int anser(int x){
        slast=query_p(1,x-1);
        ans=bsz(1,bsy(1,x,slast)-1,slast+1);
        return ans>x?ans:0;
   }
}Sherry;
inline int mp(char c){
    return c=='('?1:-1;
}
int main(){
    scanf("%d%d",&n,&m);
    scanf("%s",s+1);
    for(int i=1;i<=n;i++)
        qzh[i]=qzh[i-1]+mp(s[i]);
    Sherry.init(1,1,n);
    while(m--){
        scanf("%d%d",&op,&x);
        if(op==2){
            printf("%d Sherry\n",Sherry.anser(x));
            continue;
        }
        scanf("%d",&y);
        Sherry.modify(y);
        Sherry.modify(x-1);
    }
    return 0;
}