P8765 [蓝桥杯 2021 国 AB] 翻转括号序列
Wf_yjqd
·
·
题解
比较基础的线段树板子。
若用 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_x$，然后用懒惰标记处理区间加就行。
总体复杂度 $\operatorname{O}(m\times\log n)$。
------------
码量还行吧（可能线段树本身长），基本就板子。
```cpp
#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;
}
```