题解：AT_abc470_g [ABC470G] ΣШX

int4399 · 2026-08-10 07:51:24 · 题解

原题大战。

题意：求所有区间的 \text {mex} 之和。

经典结论就是 \text{mex}(l,r)\le \text{mex}(l,r+1)，我们考虑枚举左端点，维护所有右端点此时的答案。初始我们先求出 \text{mex}(1,i)。

考虑移动左端点会发生什么。记 nxt_i=\min\limits_{j>i,a_i=a_j} j，那么删掉 l 对 [nxt_i,n] 的数都没有影响，只会对 [i+1,nxt_i-1] 的数做一些操作。

具体分析，若一个位置原本的 \text{mex} 比 a_l 小，那你删了 a_l 根本没有影响，因此我们只需要找到 [i+1,nxt_i-1] 中 >a_i 的数，把他们推平为 a_i。又因为 \text{mex} 在固定左端点时是单调的，因此满足条件的数构成一个区间，我们只需要维护：区间推平，查询区间和，树上二分即可。复杂度 O(n\log n)。

#include<bits/stdc++.h>
#define int long long
#define mid (l+r>>1)
using namespace std;
const int N=3e5+5;
long long ans;
int n,a[N],mex[N],mp[N],nxt[N],pos[N],tr[N<<2],mx[N<<2],tag[N<<2];
void pushup(int u){tr[u]=tr[u<<1]+tr[u<<1|1],mx[u]=max(mx[u<<1],mx[u<<1|1]);}
void pushdown(int u,int l,int r){if(~tag[u]) tag[u<<1]=tag[u<<1|1]=tag[u],tr[u<<1]=tag[u]*(mid-l+1),tr[u<<1|1]=tag[u]*(r-mid),mx[u<<1]=mx[u<<1|1]=tag[u],tag[u]=-1;}
void build(int u,int l,int r){tag[u]=-1;if(l==r){mx[u]=tr[u]=mex[l];return;}build(u<<1,l,mid),build(u<<1|1,mid+1,r);pushup(u);}
int query(int u,int l,int r,int L,int R){
    if(L<=l&&r<=R) return tr[u];pushdown(u,l,r);int res=0;
    if(L<=mid) res+=query(u<<1,l,mid,L,R);
    if(mid<R) res+=query(u<<1|1,mid+1,r,L,R);
    return res;
}int find(int u,int l,int r,int L,int R,int v){
    if(l>R||r<L||mx[u]<=v) return -1; 
    if(l==r) return l;pushdown(u,l,r);
    int res=find(u<<1,l,mid,L,R,v);
    return ~res?res:find(u<<1|1,mid+1,r,L,R,v);
}void modify(int u,int l,int r,int L,int R,int v){
    if(L<=l&&r<=R){mx[u]=v,tr[u]=v*(r-l+1),tag[u]=v;return;}pushdown(u,l,r);
    if(L<=mid) modify(u<<1,l,mid,L,R,v);
    if(mid<R) modify(u<<1|1,mid+1,r,L,R,v); 
    pushup(u);
}signed main(){
    cin>>n,pos[0]=pos[n+1]=n+1;
    for(int i=1;i<=n;i++) cin>>a[i],pos[i]=n+1;
    for(int i=1,ans=0;i<=n;i++){mp[a[i]]++;while(mp[ans]) ans++;mex[i]=ans;}
    build(1,1,n);
    for(int i=n;i;i--) nxt[i]=pos[a[i]],pos[a[i]]=i;
    for(int i=1;i<=n;i++){
        ans+=query(1,1,n,i,n);if(i==n) break;
        if(i+1<=nxt[i]-1){
            int p=find(1,1,n,i+1,nxt[i]-1,a[i]);
            if(p!=-1) modify(1,1,n,p,nxt[i]-1,a[i]);
        }
    }return cout<<ans,0;
}