题解：P12401 [COI 2025] 玻利维亚 / Bolivija

· · 题解

对于某一层，如果配对的数量为 \dfrac{n}{2}，那么该层对称。

每段连续对称的长度为 l_i，答案为 \sum \dfrac{l_i \times (l_i+1)}{2}。

直接维护配对数量为 \dfrac{n}{2} 的层不好维护，考虑到其为最大值，设 f_i 为区间内最大值组成的连续段长度，直接维护该区间的最大值对应的答案 \sum \dfrac{f_i \times (f_i+1)}{2} 即可。

合并的时候记录一下区间左侧最大值的数量和最小值即可。

（愚蠢的考场代码，在线段树里维护了一些没用的值）

#include<bits/stdc++.h>
#define int long long
#define lc p<<1
#define rc p<<1|1
using namespace std;
const int N=2e5+5,V=654205;
int n,q;
int a[N];
struct tree{
    int l,r;
    int maxn,tot;
    int lt,rt;
    int maxans;
    int ans;
    int tag;
    friend tree operator+(tree x,tree y){
        tree res;
        res.l=x.l;
        res.r=y.r;
        if(x.maxn>y.maxn){
            res.maxn=x.maxn;
            res.tot=x.tot;
            res.lt=x.lt;
            res.rt=0;
            res.maxans=x.maxans;
            if(res.maxn==n/2){
                res.ans=x.ans;
            }
            else{
                res.ans=0;
            }
        }
        else if(x.maxn<y.maxn){
            res.maxn=y.maxn;
            res.tot=y.tot;
            res.lt=0;
            res.rt=y.rt;
            res.maxans=y.maxans;
            if(res.maxn==n/2){
                res.ans=y.ans;
            }
            else{
                res.ans=0;
            }
        }
        else if(x.maxn==y.maxn){
            res.maxn=x.maxn;
            res.tot=x.tot+y.tot;
            if(x.lt==x.r-x.l+1){
                res.lt=x.lt+y.lt;
            }
            else{
                res.lt=x.lt;
            }
            if(y.rt==y.r-y.l+1){
                res.rt=y.rt+x.rt;
            }
            else{
                res.rt=y.rt;
            }
            res.maxans=x.maxans+y.maxans;
            res.maxans-=x.rt*(x.rt+1)/2;
            res.maxans-=y.lt*(y.lt+1)/2;
            res.maxans+=(x.rt+y.lt)*(x.rt+y.lt+1)/2; 
            if(res.maxn==n/2){
                res.ans=res.maxans;
            }
            else{
                res.ans=0;
            }
        }
        res.tag=0;
        return res;
    }
}t[V*4];
void pushup(int p){
    t[p]=t[lc]+t[rc];
}
void pushdown(int p){
    if(t[p].tag){
        t[lc].maxn+=t[p].tag;
        if(t[lc].maxn==n/2){
            t[lc].ans=t[lc].maxans;
        }
        else{
            t[lc].ans=0;
        }
        t[lc].tag+=t[p].tag;
        t[rc].maxn+=t[p].tag;
        if(t[rc].maxn==n/2){
            t[rc].ans=t[rc].maxans;
        }
        else{
            t[rc].ans=0;
        }
        t[rc].tag+=t[p].tag;        
        t[p].tag=0;
    }
}
void build(int p,int l,int r){
    t[p].l=l,t[p].r=r,t[p].tag=0;
    if(l==r){
        t[p].lt=t[p].rt=1;
        t[p].maxn=0;
        t[p].tot=1;
        t[p].maxans=1;
        t[p].ans=0;
        return;
    }
    int mid=(t[p].l+t[p].r)>>1;
    build(lc,l,mid);
    build(rc,mid+1,r);
    pushup(p);
}
void add(int p,int l,int r,int x){
    if(l>r){
        return;
    }
    if(l<=t[p].l&&t[p].r<=r){
        t[p].maxn+=x;
        if(t[p].maxn==n/2){
            t[p].ans=t[p].maxans;
        }
        else{
            t[p].ans=0;
        }
        t[p].tag+=x;
        return;
    }
    pushdown(p);
    int mid=(t[p].l+t[p].r)>>1;
    if(l<=mid){
        add(lc,l,r,x);
    }
    if(mid+1<=r){
        add(rc,l,r,x);
    }
    pushup(p);
    //cout<<t[p].l<<' '<<t[p].r<<' '<<t[p].maxn<<' '<<t[p].tot<<' '<<t[p].lt<<' '<<t[p].rt<<' '<<t[p].maxans<<' '<<t[p].ans<<'\n';
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build(1,1,a[(n+1)/2]); 
    for(int i=1,j=n;i<=n/2;i++,j--){
        add(1,1,min(a[i],a[j]),1);
        add(1,max(a[i],a[j])+1,a[(n+1)/2],1); 
    }
    cout<<t[1].ans<<'\n';
    while(q--){
        int x,y;
        cin>>x>>y;
        add(1,1,min(a[x],a[n-x+1]),-1);
        add(1,max(a[x],a[n-x+1])+1,a[(n+1)/2],-1);
        a[x]=y;
        add(1,1,min(a[x],a[n-x+1]),1);
        add(1,max(a[x],a[n-x+1])+1,a[(n+1)/2],1);
        cout<<t[1].ans<<'\n';
    }
    return 0;
}