結果

問題 No.1526 Sum of Mex 2
ユーザー chocoruskchocorusk
提出日時 2021-05-31 20:21:15
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 124 ms / 3,000 ms
コード長 5,032 bytes
コンパイル時間 4,186 ms
コンパイル使用メモリ 197,988 KB
実行使用メモリ 25,612 KB
最終ジャッジ日時 2024-11-08 21:33:19
合計ジャッジ時間 7,493 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
5,760 KB
testcase_01 AC 3 ms
5,760 KB
testcase_02 AC 4 ms
5,888 KB
testcase_03 AC 4 ms
6,016 KB
testcase_04 AC 4 ms
6,016 KB
testcase_05 AC 4 ms
5,760 KB
testcase_06 AC 3 ms
5,888 KB
testcase_07 AC 3 ms
5,888 KB
testcase_08 AC 4 ms
5,888 KB
testcase_09 AC 4 ms
6,016 KB
testcase_10 AC 4 ms
6,016 KB
testcase_11 AC 4 ms
6,016 KB
testcase_12 AC 4 ms
5,888 KB
testcase_13 AC 17 ms
8,320 KB
testcase_14 AC 21 ms
10,240 KB
testcase_15 AC 25 ms
10,368 KB
testcase_16 AC 118 ms
25,216 KB
testcase_17 AC 83 ms
23,536 KB
testcase_18 AC 11 ms
7,936 KB
testcase_19 AC 11 ms
7,148 KB
testcase_20 AC 52 ms
15,232 KB
testcase_21 AC 111 ms
24,960 KB
testcase_22 AC 59 ms
15,744 KB
testcase_23 AC 113 ms
25,216 KB
testcase_24 AC 116 ms
25,216 KB
testcase_25 AC 114 ms
24,960 KB
testcase_26 AC 112 ms
25,216 KB
testcase_27 AC 121 ms
25,344 KB
testcase_28 AC 117 ms
25,292 KB
testcase_29 AC 124 ms
25,416 KB
testcase_30 AC 114 ms
25,344 KB
testcase_31 AC 115 ms
25,344 KB
testcase_32 AC 114 ms
25,140 KB
testcase_33 AC 83 ms
25,612 KB
evil_largest RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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