题面

题目描述 蒜头是一名优秀的画家。 蒜头有一张长度为n的画卷，在位置i上画图案会获得ai的美观度。蒜头是一个有追求的人，因此他希望他的画从左往右是越来越美观的，即对于任意两个画了图案的格子l < r，有al ≤ ar。但蒜头发现，人们评判画卷的好坏，并不会只从画出的图案来考虑。具体来说，一张画卷的美观度，定义为所有画了图案的位置的美观度之和与在图上选择两个可以重复的位置使得两位置之间不存在画了图案的位置的方案数之差。现在，蒜头想要知道，他画出的画卷的最大美观度是多少。

形式化地，一段连续的长度为m的空白位置会让美观度降低m*(m+1)/2。

输入

输入的第一行是一个数n，表示序列的长度。

接下来一行n个数，第i个数表示ai。

输出

输出一行表示最大美观度。

样例输入
输入样例1
7
1 3 2 7 3 2 4
输入样例2
7
-3 -4 -2 -2 -6 -8 -1

样例输出
输出样例1
7
输出样例2
-11

提示 对于100%的数据，n<=10^6,−10, 8≤ai≤10^8。

题解

对于这题，DP式子和斜率优化不是特别难。在这里主要讲一下如何解决 l < r，保证 al ≤ ar 的问题。 这里要求 l < r 时 al < ar，一个下标，一个权值，看来是一个二维偏序问题（至于二维偏序什么的，我自己也不是太明白，先挖个坑）。有两个维度，要保证他们都有序，肯定要先排序一个维度。这里我们按权值排序然后进行CDQ分治，每次考虑[l,mid]对[mid+1,r]的贡献即可。 每次做DP时要将[l,mid]中的东西按下标排序，在从前往后斜率优化DP；这里排序时要预处理出每个区间按下标排序的结果，直接sort效率会降低。 详见代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 1000005
using namespace std;
int n,q[N],pla[N],a[N],rk[21][N];
long long f[N],ans;
inline bool cmp(int x,int y){
	return a[x]==a[y]?x<y:a[x]<a[y];
}
inline long long Y(int i){return 2*f[i]-1ll*i*i-i;}
//归并排序预处理每个区间的排序结果
inline void gsort(int l,int r,int d){
	if(l==r){
		rk[d][l]=pla[l];
		return;
	}
	int mid=l+r>>1;
	gsort(l,mid,d+1);gsort(mid+1,r,d+1);
	int ned1=l,ned2=mid+1,num=l-1;
	while(ned1<=mid&&ned2<=r){
		if(rk[d+1][ned1]<rk[d+1][ned2]) rk[d][++num]=rk[d+1][ned1++];
		else rk[d][++num]=rk[d+1][ned2++];
	}
	while(ned1<=mid) rk[d][++num]=rk[d+1][ned1++];
	while(ned2<=r) rk[d][++num]=rk[d+1][ned2++];
}
inline void let_sdp(int l,int r,int d){
	if(l==r){
		f[pla[l]]=max(f[pla[l]],a[pla[l]]-1ll*(pla[l]-1)*pla[l]/2);
		ans=max(ans,f[pla[l]]-1ll*(n-pla[l])*(n-pla[l]+1)/2);
		return;
	}
	int mid=l+r>>1;
	let_sdp(l,mid,d+1);
	int hd=1,tl=0,j=l;
	q[0]=q[1]=0;
	for(int k=mid+1;k<=r;k++){
		int i=rk[d][k];
		while(j<=mid&&rk[d][j]<i){
			long long w=rk[d][j];
			while(hd<tl&&((Y(w)-Y(q[tl]))*(q[tl]-q[tl-1])>=(Y(q[tl])-Y(q[tl-1]))*(w-q[tl]))) tl--;
			q[++tl]=w;
			j++;
		}
		while(hd<tl&&(Y(q[hd+1])-Y(q[hd])>=-2ll*i*(q[hd+1]-q[hd]))) hd++;
		if(hd<=tl&&hd) f[i]=max(f[i],f[q[hd]]+a[i]-1ll*(i-q[hd]-1)*(i-q[hd])/2);
		ans=max(ans,f[i]-1ll*(n-i)*(n-i+1)/2);
	}
	let_sdp(mid+1,r,d+1);
}//要注意数组里装的东西，是下标还是权值；同时要明确数组的意义，不然会在小细节上出锅
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		pla[i]=i;
		f[i]=-1e14;
	}
	sort(pla+1,pla+n+1,cmp);
	ans=-1ll*n*(n+1)/2;
	gsort(1,n,0);//这里是0
	let_sdp(1,n,1);//这里是1
	//第0层时就保证[1,n]有序
	//第1层时保证[1,mid]和[mid+1,r]分别有序
	//因为DP第一层就要用[l,mid]来更新[mid+1,r],所以要用1
	printf("%lld\n",ans);
	return 0;
}

水平有限，讲的不好，还请指教，不胜感激。