結果

問題 No.1526 Sum of Mex 2
ユーザー chocorusk
提出日時 2021-05-31 20:21:15
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 161 ms / 3,000 ms
コード長 5,032 bytes
コンパイル時間 5,334 ms
コンパイル使用メモリ 191,324 KB
最終ジャッジ日時 2025-01-21 20:51:02
ジャッジサーバーID
（参考情報） 		judge1 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 31 RE * 1
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#include <list>
#include <atcoder/all>
#define popcount __builtin_popcount
using namespace std;
using namespace atcoder;
typedef long long ll;
typedef pair<int, int> P;
struct SegmentTreeBeats{ // range chmin chmax add sum
	int sz;
	vector<ll> seg, mn, mn2, mx, mx2, lazy;
	vector<int> mnc, mxc;
	const ll INF=1e18;

	SegmentTreeBeats(int n){
		sz=1;
		while(sz<n) sz<<=1;
		seg.resize(2*sz-1);
		mn.resize(2*sz-1, INF);
		mn2.resize(2*sz-1, INF);
		mx.resize(2*sz-1, -INF);
		mx2.resize(2*sz-1, -INF);
		lazy.resize(2*sz-1);
		mnc.resize(2*sz-1, 1);
		mxc.resize(2*sz-1, 1);
	}

	void merge(int k){
		if(k>=sz-1) return;
		seg[k]=seg[2*k+1]+seg[2*k+2];
		mn[k]=min(mn[2*k+1], mn[2*k+2]);
		if(mn[2*k+1]>mn[2*k+2]){
			mn2[k]=min(mn[2*k+1], mn2[2*k+2]);
			mnc[k]=mnc[2*k+2];
		}else if(mn[2*k+1]<mn[2*k+2]){
			mn2[k]=min(mn2[2*k+1], mn[2*k+2]);
			mnc[k]=mnc[2*k+1];
		}else{
			mn2[k]=min(mn2[2*k+1], mn2[2*k+2]);
			mnc[k]=mnc[2*k+1]+mnc[2*k+2];
		}
		mx[k]=max(mx[2*k+1], mx[2*k+2]);
		if(mx[2*k+1]>mx[2*k+2]){
			mx2[k]=max(mx2[2*k+1], mx[2*k+2]);
			mxc[k]=mxc[2*k+1];
		}else if(mx[2*k+1]<mx[2*k+2]){
			mx2[k]=max(mx[2*k+1], mx2[2*k+2]);
			mxc[k]=mxc[2*k+2];
		}else{
			mx2[k]=max(mx2[2*k+1], mx2[2*k+2]);
			mxc[k]=mxc[2*k+1]+mxc[2*k+2];
		}
	}

	void build(vector<ll> v){
		for(int k=0; k<v.size(); k++){
			seg[k+sz-1]=v[k];
			mn[k+sz-1]=v[k];
			mx[k+sz-1]=v[k];
		}
		for(int k=sz-2; k>=0; k--){
			merge(k);
		}
	}

	void node_chmin(int k, int l, int r, ll x){
		if(mx[k]==mn[k]){
			mx[k]=mn[k]=x;
			seg[k]=x*(r-l);
		}else if(mx[k]==mn2[k]){
			seg[k]-=(mx[k]-x)*mxc[k];
			mx[k]=mn2[k]=x;
		}else{
			seg[k]-=(mx[k]-x)*mxc[k];
			mx[k]=x;
		}
	}

	void node_chmax(int k, int l, int r, ll x){
		if(mx[k]==mn[k]){
			mx[k]=mn[k]=x;
			seg[k]=x*(r-l);
		}else if(mn[k]==mx2[k]){
			seg[k]+=(x-mn[k])*mnc[k];
			mn[k]=mx2[k]=x;
		}else{
			seg[k]+=(x-mn[k])*mnc[k];
			mn[k]=x;
		}
	}

	void push(int k, int l, int r){
		if(lazy[k]!=0){
			seg[k]+=lazy[k]*(r-l);
			mn[k]+=lazy[k];
			mn2[k]+=lazy[k];
			mx[k]+=lazy[k];
			mx2[k]+=lazy[k];
			if(k<sz-1){
				lazy[2*k+1]+=lazy[k];
				lazy[2*k+2]+=lazy[k];
			}
			lazy[k]=0;
		}
		if(k<sz-1){
			if(mn[k]>mn[2*k+1]+lazy[2*k+1]){
				node_chmax(2*k+1, l, (l+r)/2, mn[k]-lazy[2*k+1]);
			}
			if(mn[k]>mn[2*k+2]+lazy[2*k+2]){
				node_chmax(2*k+2, (l+r)/2, r, mn[k]-lazy[2*k+2]);
			}
			if(mx[k]<mx[2*k+1]+lazy[2*k+1]){
				node_chmin(2*k+1, l, (l+r)/2, mx[k]-lazy[2*k+1]);
			}
			if(mx[k]<mx[2*k+2]+lazy[2*k+2]){
				node_chmin(2*k+2, (l+r)/2, r, mx[k]-lazy[2*k+2]);
			}
		}
	}

	void chmin(int a, int b, const ll &x, int k, int l, int r){
		push(k, l, r);
		if(r<=a || b<=l || mx[k]<=x) return;
		if(a<=l && r<=b && mx2[k]<x){
			node_chmin(k, l, r, x);
			push(k, l, r);
		}else{
			chmin(a, b, x, 2*k+1, l, (l+r)/2);
			chmin(a, b, x, 2*k+2, (l+r)/2, r);
			merge(k);
		}
	}

	void chmax(int a, int b, const ll &x, int k, int l, int r){
		push(k, l, r);
		if(r<=a || b<=l || mn[k]>=x) return;
		if(a<=l && r<=b && mn2[k]>x){
			node_chmax(k, l, r, x);
			push(k, l, r);
		}else{
			chmax(a, b, x, 2*k+1, l, (l+r)/2);
			chmax(a, b, x, 2*k+2, (l+r)/2, r);
			merge(k);
		}
	}

	void add(int a, int b, const ll &x, int k, int l, int r){
		push(k, l, r);
		if(r<=a || b<=l) return;
		if(a<=l && r<=b){
			lazy[k]+=x;
			push(k, l, r);
		}else{
			add(a, b, x, 2*k+1, l, (l+r)/2);
			add(a, b, x, 2*k+2, (l+r)/2, r);
			merge(k);
		}
	}

	ll sum(int a, int b, int k, int l, int r){
		push(k, l, r);
		if(b<=l || r<=a) return 0;
		if(a<=l && r<=b) return seg[k];
		else return sum(a, b, 2*k+1, l, (l+r)/2)+sum(a, b, 2*k+2, (l+r)/2, r);
	}

	void chmin(int a, int b, const ll &x){
		return chmin(a, b, x, 0, 0, sz);
	}
	void chmax(int a, int b, const ll &x){
		return chmax(a, b, x, 0, 0, sz);
	}
	void add(int a, int b, const ll &x){
		return add(a, b, x, 0, 0, sz);
	}
	ll sum(int a, int b){
		return sum(a, b, 0, 0, sz);
	}
	ll operator[](const int &k){
		return sum(k, k+1);
	}
};
int main()
{
    int n; cin>>n;
    int a[100010];
    for(int i=0; i<n; i++){
        cin>>a[i];
    }
    vector<int> v[100010];
    for(int i=0; i<n; i++) v[a[i]].push_back(i);
    for(int i=1; i<=n; i++) v[i].push_back(n);
    int ind[100010];
    vector<ll> x(n);
    for(int i=0; i<n; i++){
        ind[i]=0;
        x[i]=v[i+1][0];
        if(i) x[i]=max(x[i], x[i-1]);
    }
    SegmentTreeBeats seg(n);
    seg.build(x);
    ll ans=0;
    for(int i=0; i<n; i++){
        ll s=(ll)n*(n+1)-i-seg.sum(0, n);
        ans+=s;
        ind[a[i]-1]++;
        seg.chmax(a[i]-1, n, v[a[i]][ind[a[i]-1]]);
    }
    cout<<ans<<endl;
    return 0;
}
0