打 ABC 的时候脑抽想出了一个神秘做法并 AC 但是不知道为啥复杂度是对的。

具体来说就是随机给每个点先分配一个 $d_i$,我才用了给前两个点分配 $1$，后面的点分配 $2$，的做法。

然后之后的调整必然是一个点度+，一个点度-。

将这两个的贡献单独拆开分别放到一个小根堆和一个大根堆，然后每次取出堆头比大小，如果调整可以更优就调整，不能就结束。

这个堆需要写一个可删堆维护。

正确性应该是没啥问题

复杂度的话就不会了，因为和调整次数有关系。

感性理解的话就是一个点如果和最优解比是多余的，那么一定会一次到位补到和最优解比是不足的位置上。

代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e5+10;
typedef pair<int,int> PII;
struct Heap1
{
	priority_queue<PII> q1,q2;
	void ins(int x,int y)
	{
		q1.push({x,y});
	}
	void del(int x,int y)
	{
		q2.push({x,y});
	}
	PII top()
	{
		while(q1.size()&&q2.size()&&q1.top()==q2.top()) q1.pop(),q2.pop();
		return q1.top();
	}
	int sz()
	{
		return q1.size()-q2.size();
	}
}H1;
struct Heap2
{
	priority_queue<PII,vector<PII>,greater<PII>> q1,q2;
	void ins(int x,int y)
	{
		q1.push({x,y});
	}
	void del(int x,int y)
	{
		q2.push({x,y});
	}
	PII top()
	{
		while(q1.size()&&q2.size()&&q1.top()==q2.top()) q1.pop(),q2.pop();
		return q1.top();
	}
	int sz()
	{
		return q1.size()-q2.size();
	}
}H2;
int n;
int A[N];
int d[N];
int res;

void insert(int i)
{
	if(d[i]>1) //可以变小,代价变小 
	{
		//printf("- %d %d\n",i,(2*d[i]-1)*A[i]);
		H1.ins((2*d[i]-1)*A[i],i);
	}
	if(d[i]<n) //可以变大，代价变大 
	{
		//printf("+ %d %d\n",i,(2*d[i]+1)*A[i]);
		H2.ins((2*d[i]+1)*A[i],i);
	}
}

void remove(int i)
{
	if(d[i]>1) //可以变小,代价变小 
	{
		//printf("- %d %d\n",i,(2*d[i]-1)*A[i]);
		H1.del((2*d[i]-1)*A[i],i);
	}
	if(d[i]<n) //可以变大，代价变大 
	{
		//printf("+ %d %d\n",i,(2*d[i]+1)*A[i]);
		H2.del((2*d[i]+1)*A[i],i);
	}
}

signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>A[i];
	
	for(int i=1;i<=n;i++)
	{
		if(i<=2) d[i]=1;
		else d[i]=2;
		res+=d[i]*d[i]*A[i];
		insert(i);
	}
	
	//printf("%d %d\n",H1.top().first,H2.top().first);
	
	while(H1.sz() && H2.sz() &&H1.top().first>H2.top().first)
	{
		auto T1=H1.top(),T2=H2.top();
		res+=-T1.first+T2.first;
		int i=T1.second,j=T2.second;
		remove(i),remove(j);
		d[i]--,d[j]++;
		insert(i),insert(j);
	}
	
	cout<<res<<"\n";
	
	return 0;
}

如果是假的请大佬给出 hack 如果是真的求证明。