题解：AT_abc470_g [ABC470G] ΣШX

· · 题解

AT_abc470_g [ABC470G] ΣШX

思路

有一个简单的暴力就是枚举 l，枚举 r，然后算区间 \operatorname{mex}，但是这样复杂度显然是不对的。

我们不妨先预处理出来当 l 为 1 的时候的每个 r 的区间 \operatorname{mex}，这个显然是可以直接 O(n) 求的。那么我们考虑当 l 往右移时，哪些 \operatorname{mex} 会变化，我们发现当一个 r 与其前面元素所对应的区间在删掉 a_l 这个值后仍然包含一个 a_l，那么 \operatorname{mex} 显然是不会变化的。那么我们只需要考虑删掉 a_l 后 r 与其前面元素所对应的区间不包含 a_l 的情况。

分类讨论一下：

上述讨论都是对于删掉 a_l 后区间内不包含 a_l 这个值所做的讨论。

之后我们发现随着 r 的递增，区间 \operatorname{mex} 一定是单调不减的，所以我们不妨预处理出当前位置 l 的下一个 a_l 出现的位置，对于这个位置的前一个一直到 l 就是我们要进行更新的 \operatorname{mex}，由于 \operatorname{mex} 单调不减这个性质，所以我们可以使用二分来解决，然后线段树区间修改即可。

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define lowbit(x) (x&(-x))
#define ls (u<<1)
#define rs (u<<1|1)
#define pii pair<int,int>
#define all(v) v.begin(),v.end()
int read(){
    int k=0,f=1;
    char c=getchar();
    while(c<'0' || c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') k=k*10+c-'0',c=getchar();
    return k*f;
}
void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x<10) putchar(x+'0');
    else write(x/10),putchar(x%10+'0');
}
const int N=3e5+10;
int a[N],mex[N],vis[N],nxt[N],nxtV[N];
struct SegMentTree{
    int val[N<<2],tag[N<<2];
    inline void pushup(int p){val[p]=val[p<<1]+val[p<<1|1];}
    inline void apply(int p,int l,int r,int k){
        val[p]=(r-l+1)*k;
        tag[p]=k;
    }
    inline void pushdown(int p,int l,int r){
        int mid=(l+r)>>1;
        if (tag[p]!=-1){
            apply(p<<1,l,mid,tag[p]);
            apply(p<<1|1,mid+1,r,tag[p]);
            tag[p]=-1;
        }
    }
    inline void build(int p,int l,int r){
        tag[p]=-1;
        if (l==r){val[p]=mex[l];return ;}
        int mid=(l+r)>>1;
        build(p<<1,l,mid);build(p<<1|1,mid+1,r);
        pushup(p);
    }
    inline int query(int p,int l,int r,int L,int R){
        if (L<=l && r<=R) return val[p];
        int mid=(l+r)>>1;
        pushdown(p,l,r);
        int res=0;
        if (L<=mid) res+=query(p<<1,l,mid,L,R);
        if (R>mid) res+=query(p<<1|1,mid+1,r,L,R);
        return res;
    }
    inline void update(int p,int l,int r,int L,int R,int k){
        if (L>R) return ;
        if (L<=l && r<=R){val[p]=(r-l+1)*k;tag[p]=k;return ;}
        int mid=(l+r)>>1;
        pushdown(p,l,r);
        if (L<=mid) update(p<<1,l,mid,L,R,k);
        if (R>mid) update(p<<1|1,mid+1,r,L,R,k);
        pushup(p);
    }
}tr;
void solve(){
    int n=read();
    for (int i=1;i<=n;i++) a[i]=read();
    int now=0;
    for (int i=1;i<=n;i++){
        vis[a[i]]=1;
        while (vis[now]) now++;
        mex[i]=now;
    }
    tr.build(1,1,n);
    for (int i=1;i<=n;i++) nxtV[a[i]]=n+1;
    for (int i=n;i>=1;i--){
        nxt[i]=nxtV[a[i]];nxtV[a[i]]=i;
    }
    int ans=0;
    for (int l=1;l<=n;l++){
        ans+=tr.query(1,1,n,l,n);
        int L=l,R=nxt[l]-1,pos=n+1;
        while (L<=R){
            int mid=(L+R)>>1;
            if (tr.query(1,1,n,mid,mid)>a[l]) pos=mid,R=mid-1;
            else L=mid+1;
        }
        tr.update(1,1,n,pos,nxt[l]-1,a[l]);
    }
    write(ans);
}
signed main(){
    int T=1;
    while (T--) solve();
    return 0;
}