p7962 noip 2021 方差

明天就比赛了，闲着打暴力,但是不会打这一题的, 用随机数搜了28分!!

#include<iostream>
#define ll long long
using namespace std;
ll n,val[2005],minn = 999999999999999;
struct node{
	ll pf;
	ll sum;
}a[500005];


void build(ll x,ll l,ll r){
	
	if(l == r)
	{
		a[x].sum = val[l];
		a[x].pf = a[x].sum*a[x].sum;
		return ;
	}
	ll mid = (l + r) / 2;
	build(2*x,l,mid);
	build(2*x+1,mid+1,r);
	a[x].sum = a[2*x].sum + a[2*x+1].sum;
	a[x].pf = a[2*x].pf + a[2*x+1].pf;
	return ;
}

void xiug(ll x,ll l,ll r,ll y,ll z){
	
	if(l == r)
	{
		a[x].sum += z;
		a[x].pf = a[x].sum*a[x].sum;
		return ;
	}
	ll mid = (l + r) / 2;
	if(y <= mid)
	{
		xiug(2*x,l,mid,y,z);
	} else
	{
		xiug(2*x+1,mid+1,r,y,z);
	}
	
	a[x].sum = a[2*x].sum + a[2*x+1].sum;
	a[x].pf = a[2*x].pf + a[2*x+1].pf;
	return ;
}


int main(){
	cin >> n;
//	freopen("air.in","r",stdin);
//	freopen("air.out","w",stdout);
	
	for(int i = 1; i <= n; i++)
	{
		cin >> val[i];
	}
	
	build(1,1,n);
	ll z;
	for(int k = 1; k <= 5000000; k++)
	{
			
			int i = rand()%(n-1) + 2;
			
			z = val[i - 1] + val[i + 1] - 2 * val[i];
			val[i] += z;
			xiug(1,1,n,i,z);
			if(minn > n*a[1].pf - a[1].sum*a[1].sum)
			{
				minn = n*a[1].pf - a[1].sum*a[1].sum;
				k = 1;
			}
//			minn = min(minn,n*a[1].pf - a[1].sum*a[1].sum);
		
//		for(int i = n - 1; i > 1; i--)
//		{
//			z = val[i - 1] + val[i + 1] - 2 * val[i];
//			val[i] += z;
//			xiug(1,1,n,i,z);
//			minn = min(minn,n*a[1].pf - a[1].sum*a[1].sum);
//		}
		
	}
	
	cout << minn << endl;
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}