P8275 [USACO22OPEN] 262144 Revisited P

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e5 + 10, M = 1e6 + 50;
inline int read()
{
	int s = 0, w = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9') { if(ch == '-') w *= -1; ch = getchar(); }
	while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
	return s * w;
}
struct node{ //并查集 
	int fa[N], siz[N];
	inline void initial(int n){
		for(register int i = 0; i < n; i++) fa[i] = i, siz[i] = 1;
	}
	inline int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
	inline void merge(int x, int y){
		int fx = find(x), fy = find(y);
		if(fx == fy) return; //已经合并过
		if(siz[fx] > siz[fy]) swap(fx, fy);
		fa[fx] = fy, siz[fy] += siz[fx], siz[fx] = 0; 
	}
}T;
int n, ans;
int L[N], R[N], arr[N];
set<int> s; //储存极值为 v 的极长子段 
vector<int> vec[M];
inline int Get_R(int x)
{
	if(x == n) return n;
	return R[T.find(x)];
}
signed main()
{
	memset(L, -1, sizeof(L)), memset(R, -1, sizeof(R));
	n = read();
	for(register int i = 0; i < n; i++) arr[i] = read();
	for(register int i = 0; i < n; i++) vec[arr[i]].push_back(i); 
	T.initial(n);
	//M -> 最大值，值的极限 
	for(register int v = 1; v <= M - 1; v++){
		vector<int> ed, tem;
		int res = 0; //记录有多少个值为 v 的区间 
		for(register int x : s){ //遍历值为 v - 1 的极大区间的左端点 
			int r = Get_R(x); //找到右端点 + 1
			int nexr = max(r, r == n ? -1 : Get_R(r)); //倍增标记是否触底 
			if(nexr == r) ed.push_back(x); //为末端区间
			else{
				if(L[nexr] != -1) ed.push_back(x); //被标记过，需要被合并
				else L[nexr] = x, tem.push_back(nexr); //未被标记过，标记 
				res += (nexr - r) * T.siz[T.find(x)], R[T.find(x)] = nexr;
			}
		}
		for(register int x : ed){ //合并 
			s.erase(x);
			if(L[Get_R(x)] == -1) L[Get_R(x)] = x; 
			else T.merge(L[Get_R(x)], x);
		}
		for(register int x : tem) L[x] = -1; //清空标记 
		for(register int x : vec[v]){ //放入 arr[x] = v 的 x  
			++res, R[x] = (x + 1), s.insert(x);
			if(L[x] != -1) s.insert(L[x]);
			L[x] = -1; //清空标记 
		}
		ans = ans + res * v;
	}
	printf("%lld\n", ans);
	return 0;
}