题解：P14761 [Opoi 2025] CCD 的序列
Recall_cpp
·
·
题解
比较板的平衡树题，比 A 好想。
首先括号序列有个非常典的套路，就是将左括号设为 1，右括号设为 -1。
合法就相当于前缀和的最小值 \ge 0，且序列总和 =0。
然后插入操作是先插 1，再插 -1，所以保证了合法性。
鉴于有插入操作，考虑用平衡树维护整个串。
如果 l=r，相当于两个括号插在一块，正好匹配上，没有改变匹配的。
否则，设子串 [l+1,r] 中有 x 个未匹配的左括号，y 个未匹配的右括号。
则插入的左括号会使这 y 个未匹配的右括号在原串中匹配的左括号往前移一个，插入的右括号同理。
这时，原串匹配最靠里的未匹配左右括号的括号就没有能匹配的了，所以它们两个要匹配起来。
答案即为 2x+2y。
代码如下。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define p_q priority_queue
#define pb push_back
#define mk make_pair
#define pii pair<int,int>
#define ve vector
#define endl '\n'
#define fi first
#define se second
#define INF 0x3f3f3f3f
#define lowbit(x) (x&(-x))
namespace cute_fzj_kuai_ruarua{
int n;
int ls[400005],rs[400005],cnt=0,key[400005],val[400005],siz[400005];
int sum[400005],lmn[400005],rmx[400005],root;
void pushup(int x){
siz[x]=siz[ls[x]]+siz[rs[x]]+1;
sum[x]=sum[ls[x]]+sum[rs[x]]+val[x];
if(!ls[x]&&!rs[x]){
lmn[x]=min(0,val[x]);
rmx[x]=max(0,val[x]);
}else{
lmn[x]=0;
rmx[x]=0;
}
if(ls[x]){
lmn[x]=min(lmn[x],lmn[ls[x]]);
lmn[x]=min(lmn[x],sum[ls[x]]+val[x]);
rmx[x]=max(rmx[x],rmx[ls[x]]+val[x]+sum[rs[x]]);
}
if(rs[x]){
rmx[x]=max(rmx[x],rmx[rs[x]]);
rmx[x]=max(rmx[x],sum[rs[x]]+val[x]);
lmn[x]=min(lmn[x],sum[ls[x]]+val[x]+lmn[rs[x]]);
}
}
int newnode(int x){
cnt++;
val[cnt]=x;
siz[cnt]=1;
sum[cnt]=x;
lmn[cnt]=min(0,x);
rmx[cnt]=max(0,x);
key[cnt]=rand();
return cnt;
}
void split(int x,int v,int &l,int &r){
if(!x){
l=0;
r=0;
return ;
}
if(siz[ls[x]]>=v){
r=x;
split(ls[x],v,l,ls[x]);
}else{
l=x;
split(rs[x],v-siz[ls[x]]-1,rs[x],r);
}
pushup(x);
}
int merge(int x,int y){
if(!x||!y) return x|y;
if(key[x]>key[y]){
rs[x]=merge(rs[x],y);
pushup(x);
return x;
}else{
ls[y]=merge(x,ls[y]);
pushup(y);
return y;
}
}
void debug(int x){
if(!x) return ;
debug(ls[x]);
if(x==root) cout<<"Root";
cout<<lmn[x]<<" "<<rmx[x]<<" "<<val[x]<<endl;
debug(rs[x]);
}
void main(){
srand(time(0));
int n;
cin>>n;
while(n--){
int l,r;
cin>>l>>r;
int x,y,z;
if(l==r){
split(root,l,x,y);
cout<<0<<endl;
root=merge(x,merge(merge(newnode(1),newnode(-1)),y));
// debug(root);
continue;
}
split(root,r,y,z);
split(y,l,x,y);
root=y;
// debug(y);
cout<<2*(-lmn[y]+rmx[y])<<endl;
root=merge(merge(x,newnode(1)),merge(y,merge(newnode(-1),z)));
// debug(root);
}
}
}
using namespace cute_fzj_kuai_ruarua;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cute_fzj_kuai_ruarua::main();
return 0;
}
```