A90507 正经题解

题意分析
这道题是$USACO$铂金组的题目，据网上分析是2048游戏的拓展版本，但我认为更像合并石子。
AC代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 3e5+10, M = 1e6+50;
inline ll read(){
	ll 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];
	void initial(int n){
		for(int i = 0; i < n; i++) fa[i] = i, siz[i] = 1;
	}
	int find(int x) {
        return fa[x]==x?x:fa[x] = find(fa[x]);
    }
	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;
ll n, ans;
ll L[N], R[N], arr[N];
set<ll> s; //储存极值为v的极长子段 
vector<ll> vec[M];

ll Get_R(ll 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(int i=0;i<n;i++) 
        arr[i] = read();
	for(int i=0;i<n;i++) 
        vec[arr[i]].push_back(i); 
	T.initial(n);
	//M -> 最大值，值的极限 
	for(int v=1;v<=M-1;v++){
		vector<ll> ed, tem;
		ll res = 0; //记录有多少个值为 v 的区间 
		for(int x : s){ //遍历值为 v - 1 的极大区间的左端点 
			ll r = Get_R(x); //找到右端点 + 1
			ll 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(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(int x:tem) L[x] = -1; //清空标记 
		for(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", ans);
	return 0;
}

既然都只想要代码那就拿吧