题解：AT_abc470_g [ABC470G] ΣШX

· · 题解

前情提要

你以飞快的速度写完了 ABCDEF。

你看了 G。
你发现 G 你貌似会。
你不摆了。你开想。

思路

啊。是这么个东西。

\sum_{1\le l\le r\le n}\operatorname{mex}(a_l,\cdots,a_r)

好传奇啊。
不过我记得 \operatorname{mex} 有单调性。
也就是说在一个区间随便加数，区间 \operatorname{mex} 值单调不减。
啊貌似可以双指针状物。
总之先固定 l。

哦等会，我记得好像如果区间每缺少一个值，若区间只有一个值，\operatorname{mex}'=\min\{\operatorname{mex},x\}。
哦这很好。

我们可以暴力算出左端点 l=1 右端点随便的值。
我们可以枚举左端点然后算出每一个右端点对应的 \operatorname{mex} 值。 对于左端点每一次加一，也就是缺少了左端点的值，即 a_l。
那么我们可以查一下下一个值也为 a_l 的位置 r。
我们可以对右端点属于 (l,r) 的 \operatorname{mex} 值进行与 a_l 取 \min 操作。
注意是开区间。

这是好做的。
类似这个题，并根据我之前写的题解，我们可以写出线段树二分或线段树上二分。
等会这不是我之前模拟赛的题吗。

我赢了！

啊我要赢了吗？！ 

#include <bits/stdc++.h>
#define SACRIFICING using
#define THE namespace
#define ROOK std
SACRIFICING THE ROOK;
typedef long long ll;
int n;
int a[300009];
vector<int>de[300009];
bool vis[300009];
int sd[300009];
int lz[1200009];
struct node{
    int maxn;
    int minn;
    ll sum;
}tr[1200009];
inline void puup(int pos){
    tr[pos].maxn=max(tr[pos<<1].maxn,tr[pos<<1|1].maxn);
    tr[pos].minn=min(tr[pos<<1].minn,tr[pos<<1|1].minn);
    tr[pos].sum=tr[pos<<1].sum+tr[pos<<1|1].sum;
}
inline void pudo(int pos,int l,int r){
    if(lz[pos]!=-1){
        int mid=(l+r)>>1;
        lz[pos<<1]=lz[pos<<1|1]=lz[pos];
        tr[pos<<1].sum=1ll*(mid-l+1)*lz[pos];
        tr[pos<<1|1].sum=1ll*(r-mid)*lz[pos];
        tr[pos<<1].minn=tr[pos<<1|1].minn=tr[pos<<1].maxn=tr[pos<<1|1].maxn=lz[pos];
        lz[pos]=-1;
    }
}
inline void build(int pos,int l,int r){
    lz[pos]=-1;
    tr[pos].maxn=0;
    tr[pos].minn=400009;
    if(l>r)return ;
    if(l==r){
        tr[pos].maxn=tr[pos].minn=tr[pos].sum=sd[l];
        return ;
    }
    build(pos<<1,l,(l+r)>>1);
    build(pos<<1|1,(l+r)/2+1,r);
    puup(pos);
}
inline ll que(int pos,int l,int r,int sl,int sr){
    if(l>r||l>sr||r<sl)return 0;
    if(l>=sl&&r<=sr){
        return tr[pos].sum;
    }
    pudo(pos,l,r);
    return que(pos<<1,l,(l+r)>>1,sl,sr)+que(pos<<1|1,(l+r)/2+1,r,sl,sr);    
}
inline void upd(int pos,int l,int r,int sl,int sr,int k){
   // cout<<tr[pos].maxn<<' '<<l<<" "<<r<<'\n';
    if(l>r||l>sr||r<sl||tr[pos].maxn<=k)return ;

    if(l>=sl&&r<=sr&&tr[pos].minn>=k){
        tr[pos].maxn=tr[pos].minn=k;
        tr[pos].sum=1ll*(r-l+1)*k;
        //cout<<l<<' '<<r<<' '<<k<<'\n';
        lz[pos]=k;
        return ;
    }
    pudo(pos,l,r);
    upd(pos<<1,l,(l+r)>>1,sl,sr,k);
    upd(pos<<1|1,(l+r)/2+1,r,sl,sr,k);
    puup(pos);
}
ll ans=0;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=n;i>=1;i--){
        de[a[i]].push_back(i); 
    }
    int curans=0;
    for(int i=1;i<=n;i++){
        vis[a[i]]=1;
        for(;curans<=n;curans++){
            if(!vis[curans])break;
        }
        sd[i]=curans;
    }
    build(1,1,n);
    ans+=tr[1].sum;
    for(int i=2;i<=n;i++){
        de[a[i-1]].pop_back();
        int kf;
        if(!de[a[i-1]].empty())kf=de[a[i-1]].back();
        else kf=n+1;
        //cout<<i<<' '<<kf<<' '<<a[i-1]<<'\n';
        upd(1,1,n,i,kf-1,a[i-1]);
        ans+=que(1,1,n,i,n);
    }
    printf("%lld",ans);
    return 0;
}

后记

少年，你醒了。
想啥呢。

你的 F 都因为猎奇错误而炸了。
然后你没看 G。

醒醒，孩子。
你的那个模拟赛题目的题解代码正解也写错了。

离黄 perf 最近的一次。
离 AK 最近的一次。

我想哭。
啊。我的黄 perf——
啊啊啊啊。（撒泼打滚）

所以求赞我的 CDEFG 题解。