斜率优化，没有细节

#include
     
      #include
      
       #include
       
        using namespace std;long long g[1000005],f[1000005],a[1000005],b[1000005],c[1000005],d[1000005],last[1000005];struct node{	long long k,b;}line[1000005];vector
        
          vec[1000005];double check(node a,node b){	double x=((double)b.b-a.b)/(a.k-b.k);	return x;}int main(){	int n;	scanf("%d",&n);	for (int i=1; i<=n; i++){		scanf("%lld",&a[i]);		c[i]=c[last[a[i]]]+1;		b[i]=c[i]+1;		d[i]=a[i]*c[i]*2;		last[a[i]]=i;	}	for (int i=1; i<=n; i++){		g[i]=f[i-1]+a[i]*c[i]*c[i];		line[i]=(node){-d[i],g[i]};		int C=a[i];		int tail=(int)vec[C].size()-1;		while (tail>=1 && check(vec[C][tail],vec[C][tail-1])<=check(line[i],vec[C][tail])) vec[C].pop_back(),tail--;		vec[C].push_back(line[i]);		int L=0,R=(int)vec[C].size()-1;		while (L
         
          >1;			double l,r;			if (mid==0) r=-1ll<<60;			else r=check(vec[C][mid],vec[C][mid-1]);			if (mid==(int)vec[C].size()-1) l= 1ll<<60;			else l=check(vec[C][mid],vec[C][mid+1]);			if (b[i]>=l && b[i]<=r) {				L=mid;				break;			}			if (b[i]>r) R=mid-1;			if (b[i]