题解：AT_abc470_g [ABC470G] ΣШX

· · 题解

abc 依旧原题大战。

全局所有子区间的答案的和，考虑扫描线。

考虑到 mex 的性质，删数容易但是加数困难，选择在一开始预处理出每一个 r 到 1 的答案，再往右做扫描线，同时维护这个答案的区间和。

发现这个就是乐子。删除集合中一个元素 x，如果是最后一个这种元素，需要 \text{mex} = \min(\text{mex},x)，否则不做任何操作。于是预处理出每个元素下一个和他相等的数的位置 las，删除 a_i，即维护的答案序列在 [i+1,las_i-1] 范围内 chkmin。

区间 chkmin 与区间和，吉司机线段树模板，复杂度 O(n \log n)。

::::success[code]

#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define inf -2000000000
#define mod 998244353
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
    for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}

int a[500010];
int v[500010];
int p[500010];
int n,q;
struct STB{
    long long s[2000010];
    int mxa[2000010],mxb[2000010],se[2000010],tag1[2000010],tag2[2000010],tag3[2000010],tag4[2000010];
    int cnt[2000010];
    inline int ls(int x){return (x<<1);}
    inline int rs(int x){return (x<<1)|1;}
    inline void pushup(int x){
        int l=ls(x),r=rs(x);
        s[x]=s[l]+s[r],mxa[x]=max(mxa[l],mxa[r]),mxb[x]=max(mxb[l],mxb[r]);
        if(mxa[l]==mxa[r])se[x]=max(se[l],se[r]),cnt[x]=cnt[l]+cnt[r];
        if(mxa[l]<mxa[r])se[x]=max(se[r],mxa[l]),cnt[x]=cnt[r];
        if(mxa[l]>mxa[r])se[x]=max(se[l],mxa[r]),cnt[x]=cnt[l];
    }
    inline void build(int x,int l,int r){
        if(l==r){
            s[x]=mxa[x]=mxb[x]=p[l];
            se[x]=inf,cnt[x]=1;
            return ;
        }
        int mid=(l+r)>>1;
        build(ls(x),l,mid);build(rs(x),mid+1,r);
        pushup(x);
    }
    inline void change(int x,int k1,int k2,int k3,int k4,int l,int r){
        s[x]+=1ll*k1*cnt[x]+1ll*k3*(r-l+1-cnt[x]);
        mxb[x]=max(mxb[x],mxa[x]+k2);
        mxa[x]+=k1;
        if(se[x]!=inf)se[x]+=k3;
        tag2[x]=max(tag1[x]+k2,tag2[x]),tag1[x]+=k1;
        tag4[x]=max(tag3[x]+k4,tag4[x]),tag3[x]+=k3;
    }
    inline void pushdown(int x,int l,int r){
        int mid=(l+r)>>1;
        int mx=max(mxa[ls(x)],mxa[rs(x)]);
        if(mx==mxa[ls(x)])change(ls(x),tag1[x],tag2[x],tag3[x],tag4[x],l,mid);
        else change(ls(x),tag3[x],tag4[x],tag3[x],tag4[x],l,mid);
        if(mx==mxa[rs(x)])change(rs(x),tag1[x],tag2[x],tag3[x],tag4[x],mid+1,r);
        else change(rs(x),tag3[x],tag4[x],tag3[x],tag4[x],mid+1,r);
        tag1[x]=0,tag2[x]=0,tag3[x]=0,tag4[x]=0;
    }
    inline long long qsum(int x,int l,int r,int ql,int qr){
        if(ql>r||qr<l)return 0;
        if(ql<=l&&r<=qr)return s[x];
        pushdown(x,l,r);
        int mid=(l+r)>>1;
        return qsum(ls(x),l,mid,ql,qr)+qsum(rs(x),mid+1,r,ql,qr);
    }
    inline void chkn(int x,int l,int r,int ql,int qr,int k){
        if(ql>r||qr<l||k>=mxa[x])return ;
        if(ql<=l&&r<=qr&&se[x]<k){
            int r=mxa[x]-k;
            s[x]-=1ll*cnt[x]*r;
            mxa[x]=k,tag1[x]-=r;
            return ;
        }
        pushdown(x,l,r);
        int mid=(l+r)>>1;
        chkn(ls(x),l,mid,ql,qr,k);chkn(rs(x),mid+1,r,ql,qr,k);
        pushup(x);
    }
}T;

int ans=0;
int las[500010];

signed main(){

    n=read();
    for(int i=1;i<=n;i++)a[i]=read();
    int as=0;
    for(int i=1;i<=n;i++){
        v[a[i]]=1;
        while(v[as])as++;
        p[i]=as;
    }
    for(int i=0;i<=n;i++)v[i]=n+1;
    for(int i=n;i>=1;i--){
        las[i]=v[a[i]];
        v[a[i]]=i;
    }
    T.build(1,1,n);
    for(int i=1;i<=n;i++){
        ans+=T.qsum(1,1,n,i,n);
        T.chkn(1,1,n,i,las[i]-1,a[i]);
    }
    cout<<ans<<'\n';
    return 0;
}

::::