洛谷 P3215 [HNOI2011]括号修复 / [JSOI2011]括号序列（fhq-treap）

题目链接

题意：有一个长度为 \(n\) 的括号序列，你需要支持以下操作：

1. 将 \([l,r]\) 中所有括号变为 \(c\)
2. 将 \([l,r]\) 区间翻转
3. 将 \([l,r]\) 区间中左括号变右括号，右括号变左括号
4. 求最少需要改变多少个括号才能使得 \([l,r]\) 变成合法括号序列，保证区间长度为偶数。
   
   \(1 \leq n \leq 10^5\)

基础的 fhq-treap 的题目，主要练下放标记的技巧。

首先我们需要将要求的东西转化为一个式子。例如括号序列 \((())))))((()\)，将左右括号抵消掉之后就是 \())))((\)，发现抵消完了之后变成了一段左括号跟一段右括号。

我们记 \((=-1\)，\()=1\)，假设前缀最大值为 \(mx\)，后缀最小值为 \(mn\)，那么最后会剩下 \(mx\) 个右括号和 \(-mn\) 个左括号，最少需要需要 \(\lceil \frac{mx}{2} \rceil+\lceil -\frac{mn}{2} \rceil\) 次操作。

我们建一棵平衡树，每个节点维护以下六个值：\(sz\) 子树大小，\(sum\) 子树权值和，\(prmn,prmx,sfmn,sfmx\) 表示前缀和后缀的最值，更新方式与最大子段和类似。

对于三个修改操作，我们考虑以下处理方式：

1. 区间赋值，直接维护标记然后更新 \(sum\) 和 最值。
2. 区间翻转操作，直接交换左右儿子和前、后缀最大最小值。
3. 区间取逆操作，实际上就是将每个点的权值变为它的相反数，它的和、前后缀最大最小值也都变为了各自的相反数，如果有赋值标记，那么赋值标记也要取反。需要注意的一点是，最大值取了个相反数之后就变成了最小值，最小值取了相反数之后就变成了最大值，因此还需 swap 一下。

细节还是挺多的，代码也调了不少时间：

//Coded by tzc_wk
/*
数据不清空，爆零两行泪。
多测不读完，爆零两行泪。
边界不特判，爆零两行泪。
贪心不证明，爆零两行泪。
D P 顺序错，爆零两行泪。
大小少等号，爆零两行泪。
变量不统一，爆零两行泪。
越界不判断，爆零两行泪。
调试不注释，爆零两行泪。
溢出不 l l，爆零两行泪。
*/
#include <bits/stdc++.h>
using namespace std;
#define fifirst
#define sesecond
#define fz(i,a,b)for(int i=a;i<=b;i++)
#define fd(i,a,b)for(int i=a;i>=b;i--)
#define foreach(it,v) for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define all(a)a.begin(),a.end()
#define giveup(...) return printf(__VA_ARGS__),0;
#define fill0(a)memset(a,0,sizeof(a))
#define fill1(a)memset(a,-1,sizeof(a))
#define fillbig(a)memset(a,0x3f,sizeof(a))
#define fillsmall(a) memset(a,0xcf,sizeof(a))
#define mask(a)(1ll<<(a))
#define maskx(a,x)((a)<<(x))
#define _bit(a,x)(((a)>>(x))&1)
#define _sz(a)((int)(a).size())
#define filei(a)freopen(a,"r",stdin);
#define fileo(a)freopen(a,"w",stdout);
#define fileio(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
#define eprintf(...) fprintf(stderr,__VA_ARGS__)
#define put(x)putchar(x)
#define eoln put('\n')
#define spaceput(' ')
#define y1y_chenxiaoyan_1
#define y0y_chenxiaoyan_0
typedef pair<int,int> pii;
inline int read(){
int x=0,neg=1;char c=getchar();
while(!isdigit(c)){
if(c=='-')neg=-1;
c=getchar();
}
while(isdigit(c))x=x*10+c-'0',c=getchar();
return x*neg;
}
inline void print(int x){
if(x<0){
putchar('-');
print(abs(x));
return;
}
if(x<=9)putchar(x+'0');
else{
print(x/10);
putchar(x%10+'0');
}
}
inline int qpow(int x,int e,int _MOD){
int ans=1;
while(e){
if(e&1)ans=ans*x%_MOD;
x=x*x%_MOD;
e>>=1;
}
return ans;
}
int n=read(),m=read();
char str[100005];
struct node{
int ch[2],val,key;
int prmx,prmn,sfmx,sfmn,sum,sz;
int rv_lz,cov_lz,inv_lz;
} s[100005];
int ncnt=0,root;
inline void pushup(int k){
//s[0].prmx=s[0].sfmx=0;s[0].prmn=s[0].sfmn=0x3f3f3f3f;
s[k].prmx=max(s[s[k].ch[0]].prmx,s[s[k].ch[0]].sum+s[k].val+s[s[k].ch[1]].prmx);
s[k].prmn=min(s[s[k].ch[0]].prmn,s[s[k].ch[0]].sum+s[k].val+s[s[k].ch[1]].prmn);
s[k].sfmx=max(s[s[k].ch[1]].sfmx,s[s[k].ch[1]].sum+s[k].val+s[s[k].ch[0]].sfmx);
s[k].sfmn=min(s[s[k].ch[1]].sfmn,s[s[k].ch[1]].sum+s[k].val+s[s[k].ch[0]].sfmn);
s[k].sum=s[s[k].ch[0]].sum+s[s[k].ch[1]].sum+s[k].val;
s[k].sz=s[s[k].ch[0]].sz+s[s[k].ch[1]].sz+1;
}
inline void inv_part(int k){
s[k].val=-s[k].val;s[k].sum=-s[k].sum;
int prmn=s[k].prmn,prmx=s[k].prmx,sfmn=s[k].sfmn,sfmx=s[k].sfmx;
s[k].prmn=-prmx;s[k].prmx=-prmn;s[k].sfmn=-sfmx;s[k].sfmx=-sfmn;
s[k].cov_lz=-s[k].cov_lz;
s[k].inv_lz^=1;
}
inline void cov_part(int k,int mk){
s[k].val=mk;
s[k].sum=mk*s[k].sz;
s[k].cov_lz=mk;
if(mk==1){s[k].prmn=s[k].sfmn=0;s[k].prmx=s[k].sfmx=s[k].sum;}
else{s[k].prmx=s[k].sfmx=0;s[k].prmn=s[k].sfmn=s[k].sum;}
}
inline void rev_part(int k){
swap(s[k].ch[0],s[k].ch[1]);
swap(s[k].prmn,s[k].sfmn);
swap(s[k].prmx,s[k].sfmx);
s[k].rv_lz^=1;
}
inline void pushdown(int k){
if(s[k].inv_lz){
if(s[k].ch[0])inv_part(s[k].ch[0]);
if(s[k].ch[1])inv_part(s[k].ch[1]);
s[k].inv_lz=0;
}
if(s[k].cov_lz){
if(s[k].ch[0])cov_part(s[k].ch[0],s[k].cov_lz);
if(s[k].ch[1])cov_part(s[k].ch[1],s[k].cov_lz);
s[k].cov_lz=0;
}
if(s[k].rv_lz){
if(s[k].ch[0])rev_part(s[k].ch[0]);
if(s[k].ch[1])rev_part(s[k].ch[1]);
s[k].rv_lz=0;
}
}
inline int newnode(char c){
ncnt++;
s[ncnt].key=rand()<<15|rand();
s[ncnt].sz=1;
if(c=='('){
s[ncnt].prmn=s[ncnt].sfmn=-1;
s[ncnt].prmx=s[ncnt].sfmx=0;
s[ncnt].sum=-1;
s[ncnt].val=-1;
}
else{
s[ncnt].prmn=s[ncnt].sfmn=0;
s[ncnt].prmx=s[ncnt].sfmx=1;
s[ncnt].sum=1;
s[ncnt].val=1;
}
return ncnt;
}
inline void build(int &k,int l,int r){
int mid=(l+r)>>1;
k=newnode(str[mid]);
if(l!=mid)build(s[k].ch[0],l,mid-1);
if(r!=mid)build(s[k].ch[1],mid+1,r);
pushup(k);
}
inline void split(int k,int sz,int &a,int &b){
if(!k){
a=b=0;
return;
}
pushdown(k);
if(sz<=s[s[k].ch[0]].sz){
b=k;
split(s[k].ch[0],sz,a,s[k].ch[0]);
}
else{
a=k;
split(s[k].ch[1],sz-s[s[k].ch[0]].sz-1,s[k].ch[1],b);
}
pushup(k);
}
inline int merge(int a,int b){
pushdown(a);pushdown(b);
if(!a||!b)return a+b;
if(s[a].key<s[b].key){
s[a].ch[1]=merge(s[a].ch[1],b);
pushup(a);return a;
}
else{
s[b].ch[0]=merge(a,s[b].ch[0]);
pushup(b);return b;
}
}
inline void rev(int l,int r){
int k1,k2,k3;
split(root,l-1,k1,k2);
split(k2,r-l+1,k2,k3);
rev_part(k2);
root=merge(merge(k1,k2),k3);
}
inline void inv(int l,int r){
int k1,k2,k3;
split(root,l-1,k1,k2);
split(k2,r-l+1,k2,k3);
inv_part(k2);
root=merge(merge(k1,k2),k3);
}
inline void cov(int l,int r,int x){
int k1,k2,k3;
split(root,l-1,k1,k2);
split(k2,r-l+1,k2,k3);
cov_part(k2,x);
root=merge(merge(k1,k2),k3);
}
inline int getf(int x){
if(x&1)return (x>>1)+1;
elsereturn x>>1;
}
inline int query(int l,int r){
int k1,k2,k3;
split(root,l-1,k1,k2);
split(k2,r-l+1,k2,k3);
int res=getf(s[k2].prmx)+getf(abs(s[k2].sfmn));
root=merge(merge(k1,k2),k3);
return res;
}
signed main(){
cin>>str+1;
build(root,1,n);
while(m--){
char opt[10];cin>>opt+1;
if(opt[1]=='R'){
int l=read(),r=read();
char c;cin>>c;
if(c=='(')cov(l,r,-1);
elsecov(l,r,1);
}
if(opt[1]=='S'){
int l=read(),r=read();
rev(l,r);
}
if(opt[1]=='I'){
int l=read(),r=read();
inv(l,r);
}
if(opt[1]=='Q'){
int l=read(),r=read();
cout<<query(l,r)<<endl;
}}
return 0;
}