結果

問題 No.1526 Sum of Mex 2
ユーザー vjudge1
提出日時 2025-07-20 21:37:32
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 22 ms / 3,000 ms
コード長 2,381 bytes
コンパイル時間 1,925 ms
コンパイル使用メモリ 200,876 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-07-20 21:37:35
合計ジャッジ時間 3,498 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 31 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;
int n;
int a[200005];
int nxt[200005];
int dd[200005];
long long val;
long long ans=0;
int now[200005];
set<int>s;
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1; i<=n; i++)cin>>a[i];
    for(int i=1; i<=n+1; i++)dd[i]=n+1;
    for(int i=n; i>=1; i--)nxt[i]=dd[a[i]],dd[a[i]]=i;
    int maxx=0;
    for(int i=1; i<=n+1; i++) {
        if(dd[i]>maxx) {
            maxx=dd[i];
            s.insert(i);
        }
        now[i]=dd[i];

    }
    int pre=1;
    for(auto it=s.begin(); it!=s.end(); it++) {
        val+=(*it)*(now[*it]-pre);
        pre=now[*it];
    }
    ans=val;
    for(int i=1; i<=n-1; i++) {
        if(now[*s.begin()]>i)
            val-=(*s.begin());
        auto it=s.lower_bound(a[i]);
        if(it==s.end()) {
            ans+=val;
            continue;
        }
        if(it!=s.begin()&&now[*prev(it)]>nxt[i]){ans+=val;continue;}
        if(*it==a[i]) {
            int ll;
            int r;
            if(it==s.begin())ll=i+1;
            else ll=now[*prev(it)];
            r=*next(it);
            if(now[a[i]]>=ll)
                val-=a[i]*(now[a[i]]-ll);
            val-=r*(now[r]-now[a[i]]);
            val+=r*(now[r]-ll);
            s.erase(it++);
        }
        now[a[i]]=nxt[i];
        while(next(it)!=s.end()&&now[a[i]]>now[*it]) {
            int ll;
            int r;
            if(it==s.begin())ll=i+1;
            else ll=now[*prev(it)];
            r=*next(it);
            val-=(*it)*(now[*it]-ll);
            val-=r*(now[r]-now[*it]);
            val+=r*(now[r]-ll);
            s.erase(it++);
        }
        if(*it<a[i]) {
            ans+=val;
            continue;
        }
        if(now[a[i]]>=now[*it]) {
            int ll;
            int r;
            if(it==s.begin())ll=i+1;
            else ll=now[*prev(it)];
            val-=(*it)*(now[*it]-ll);
            val+=a[i]*(now[a[i]]-ll);
            s.erase(it);
        } else {
            int ll;
            int r;
            if(it==s.begin())ll=i+1;
            else ll=now[*prev(it)];
            r=*it;
            val-=(*it)*(now[*it]-ll);
            val+=a[i]*(now[a[i]]-ll);
            val+=r*(now[r]-now[a[i]]);
        }
        s.insert(a[i]);
        ans+=val;
        //cout<<i<<" "<<val<<'\n';
    }
    cout<<ans;
    return 0;
}
0