Submission #44114391

---

Source Code Expand

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define op(x) ((x&1)?x+1:x-1)
#define odd(x) (x&1)
#define even(x) (!odd(x))
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define lowbit(x) (x&-x)
#define mp(x,y) make_pair(x,y)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
using namespace std;

const int MAXN = 5e5+10;

int n,a[MAXN],b[MAXN];

void tomin(int& x,int y){
	x = min(x,y);
}

ll ans;

struct DSU{
	int fa[MAXN];
	void init(){
		iota(fa+1,fa+2+n,1);
	}
	int find(int x){
		return (fa[x] == x) ? (x) : (fa[x] = find(fa[x]));
	}
	void rst(int x){
		fa[x] = find(x+1);
	}
}dsu;

vector<array<int,2> >mdf[MAXN];
multiset<int>S;

set<int>R[MAXN];

void del(int x){
	dsu.rst(x);
	R[a[x]].erase(x);
}

int main(){
	cin>>n;

	rep(i,1,n){	
		cin>>a[i];
	}
	
	dsu.init();

	rep(i,1,n){
		if(a[i] > 1){
			if(R[a[i]-1].size()){
				int u = *R[a[i]-1].rbegin();
				b[i] = u;
				R[a[i]-1].erase(u);

				for(int j = dsu.find(u);j < i;j = dsu.find(j)){
					del(j);
				}
			}
		}

		R[a[i]].insert(i);
	}
	



	rep(i,1,n)if(a[i] > 1){
		mdf[b[i]+1].push_back({i-1,1});
		mdf[i+1].push_back({i-1,-1});
	}

	rep(i,1,n){
		for(auto [x,y] : mdf[i]){
			if(y == 1)S.insert(x);
			else S.erase(S.find(x));
		}
		int p = (S.size()) ? (*S.begin()) : (n);

		ans += p-i+1;
	}

	cout<<ans<<endl;

    return 0;
}

Submission Info

Judge Result