题解：P14761 [Opoi 2025] CCD 的序列

· · 题解

显然，每次操作后串仍为合法的。

我们考虑将串分为 3 段，[1,l]，[1+1,r] 与 [r+1,n]。显而易见，这次操作导致匹配发生变更的括号数为 [1+1,r] 中这次操作导致匹配发生变更的括号数 \times 2。

继续思考，我们发现我们所求的等价于求 [l+1,r] 中不匹配的 ( 与 )。我们考虑将 ( 设为 1，) 设为 -1，那么问题就转化为求 [l+1,r] 的最小前缀和与最大后缀和，平衡树维护即可。

代码如下（有旋 Treap）：

#include<bits/stdc++.h>
using namespace std;
struct node{
    int val,key;
    int sz,sum; 
    int pre_min,suf_max;
    int lc,rc;
}t[400005];
int cnt,rt;
struct trio{
    int pre_min,suf_max;
    int sum;
};
inline trio merge(trio x,trio y){//合并两个相邻区间的信息 
    return {min(x.pre_min,x.sum+y.pre_min),max(y.suf_max,y.sum+x.suf_max),x.sum+y.sum};
}
inline int newnode(int val){//创建新节点 
    t[++cnt]={val,rand()*rand(),1,val,min(val,0),max(val,0),0,0};
    return cnt;
}
inline void pushup(int p){//更新 
    t[p].sz=t[t[p].lc].sz+t[t[p].rc].sz+1;
    t[p].sum=t[t[p].lc].sum+t[t[p].rc].sum+t[p].val;
    t[p].pre_min=min(t[t[p].lc].pre_min,t[t[p].lc].sum+t[p].val+t[t[p].rc].pre_min);
    t[p].suf_max=max(t[t[p].rc].suf_max,t[t[p].rc].sum+t[p].val+t[t[p].lc].suf_max);
}
inline void zig(int &p){//左旋 
    int q=t[p].lc;
    t[p].lc=t[q].rc;
    t[q].rc=p;
    p=q;
    pushup(t[p].rc);
    pushup(p);
}
inline void zag(int &p){//右旋 
    int q=t[p].rc;
    t[p].rc=t[q].lc;
    t[q].lc=p;
    p=q;
    pushup(t[p].lc);
    pushup(p);
}
inline void insert(int &p,int k,int val){//插入 
    if(!p){
        p=newnode(val);
        return;
    }
    t[p].sz++;
    if(t[t[p].lc].sz<k){
        insert(t[p].rc,k-t[t[p].lc].sz-1,val);
        pushup(p);
        if(t[t[p].rc].key>t[p].key) zag(p);
    }
    else{
        insert(t[p].lc,k,val);
        pushup(p);
        if(t[t[p].lc].key>t[p].key) zig(p);
    }
}
inline trio query(int p,int l,int r){//查询类似SGT 
    if(!p||l>r) return {0,0,0};
    if(l<=1&&r>=t[p].sz) return {t[p].pre_min,t[p].suf_max,t[p].sum};
    trio ans,ansl,ansp,ansr;
    bool flag=0,t1=0,t2=0,t3=0;
    ans=ansl=ansp=ansr={0,0,0};
    //处理当前节点，向下查询 
    if(t[t[p].lc].sz>=l){
        ansl=query(t[p].lc,l,min(t[t[p].lc].sz,r));
        t1=1;
    }
    if(t[t[p].lc].sz>=l-1&&t[t[p].lc].sz<r){
        ansp={min(t[p].val,0),max(t[p].val,0),t[p].val};
        t2=1;
    }
    if(t[t[p].lc].sz<r-1){
        ansr=query(t[p].rc,max(1,l-t[t[p].lc].sz-1),r-t[t[p].lc].sz-1);
        t3=1;
    }
    //合并
    if(t1){
        ans=ansl;
        flag=1;
    }
    if(t2){
        if(t1) ans=merge(ans,ansp);
        else ans=ansp;
    }
    if(t3){
        if(t1||t2) ans=merge(ans,ansr);
        else ans=ansr;
    }
    return ans;
}
int main(){
    int n;
    srand(998244353);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    while(n--){
        int l,r;
        cin >> l >> r;
        if(l==r){
            cout << 0 << '\n';
        }
        else{
            trio ans=query(rt,l+1,r);
            cout << 2*(-ans.pre_min+ans.suf_max) << '\n';//记得*2
        }
        insert(rt,l,1);
        insert(rt,r+1,-1);
    }
    return 0;
}