A840.262144 Revisite

题目大意：贝西喜欢下载游戏在手机上玩，尽管她确实发现小触摸屏对于她的大蹄来说使用起来相当麻烦。她对当前正在玩的游戏特别感兴趣。游戏从 N 个正整数 a 1 ​ ,a 2 ​ ,…,a N ​ (2≤N≤262,144) 组成的序列开始，每个正整数的范围为 1…10 6 。在一次移动中，Bessie 可以取出两个相邻的数字，并将它们替换为一个比两个数字中的最大值大 1 的数字（例如，她可以用 8 替换相邻的一对 (5,7)）。游戏在 N−1 次移动后结束，此时只剩下一个数字。目标是最小化这个最终数字。贝西知道这个游戏对你来说太简单了。因此，你的工作不仅仅是在 a 上以最佳方式玩游戏，而是针对 a 的每个连续子序列。输出 a 的所有 2 N(N+1) ​个连续子序列的最小可能最终数字之和。
上AC代码：

#pragma GCC optimize(3)
#include <iostream>
#include <set>
#include <vector>
#include <string.h>
using namespace std;
const long long N = 3e5 + 10, M = 1e6 + 50;
inline long long read(){
	long long 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{ 
	long long fa[N], siz[N];
	inline void initial(long long n){
		for(register int i = 0; i < n; i++) fa[i] = i, siz[i] = 1;
	}
	inline long long find(long long x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
	inline void merge(long long x, long long y){
		long long 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;

long long n, ans;
long long L[N], R[N], arr[N];
set<long long> s;
vector<long long> vec[M];

inline long long Get_R(long long x)
{
	if(x == n) return n;
	return R[T.find(x)];
}

int main(){
	memset(L, -1, sizeof(L)), memset(R, -1, sizeof(R));
	n = read();
	for(register long long i = 0; i < n; i++) arr[i] = read();
	for(register long long i = 0; i < n; i++) vec[arr[i]].push_back(i); 
	T.initial(n);
	for(register long long v = 1; v <= M - 1; v++){
		vector<long long> ed, tem;
		long long res = 0;
		for(register long long x : s){
			long long r = Get_R(x);
			long long 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 long long 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 long long x : tem) L[x] = -1;
		for(register long long x : vec[v]){
			++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;
}