結果

問題 No.1526 Sum of Mex 2
ユーザー chocoruskchocorusk
提出日時 2021-05-31 20:21:15
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 103 ms / 3,000 ms
コード長 5,032 bytes
コンパイル時間 3,849 ms
コンパイル使用メモリ 195,404 KB
実行使用メモリ 25,608 KB
最終ジャッジ日時 2023-08-08 15:40:08
合計ジャッジ時間 6,972 ms
ジャッジサーバーID
(参考情報)
judge12 / judge15
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
5,804 KB
testcase_01 AC 2 ms
5,920 KB
testcase_02 AC 2 ms
5,820 KB
testcase_03 AC 3 ms
6,084 KB
testcase_04 AC 3 ms
6,096 KB
testcase_05 AC 2 ms
5,808 KB
testcase_06 AC 3 ms
5,928 KB
testcase_07 AC 3 ms
6,088 KB
testcase_08 AC 4 ms
5,888 KB
testcase_09 AC 3 ms
6,008 KB
testcase_10 AC 3 ms
5,868 KB
testcase_11 AC 3 ms
5,904 KB
testcase_12 AC 3 ms
6,092 KB
testcase_13 AC 16 ms
8,220 KB
testcase_14 AC 18 ms
10,240 KB
testcase_15 AC 22 ms
10,360 KB
testcase_16 AC 102 ms
24,956 KB
testcase_17 AC 73 ms
23,388 KB
testcase_18 AC 9 ms
7,900 KB
testcase_19 AC 9 ms
6,924 KB
testcase_20 AC 44 ms
14,988 KB
testcase_21 AC 97 ms
25,012 KB
testcase_22 AC 52 ms
15,832 KB
testcase_23 AC 101 ms
25,312 KB
testcase_24 AC 99 ms
25,264 KB
testcase_25 AC 97 ms
24,708 KB
testcase_26 AC 97 ms
25,052 KB
testcase_27 AC 102 ms
25,068 KB
testcase_28 AC 99 ms
25,176 KB
testcase_29 AC 103 ms
25,252 KB
testcase_30 AC 102 ms
25,316 KB
testcase_31 AC 101 ms
25,340 KB
testcase_32 AC 98 ms
24,952 KB
testcase_33 AC 80 ms
25,608 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