题目
题目描述
蒜头是一名优秀的画家
蒜头有一张长度为$n$的画卷，在位置$i$上画图案会获得$a_i$的美观度
蒜头是一个有追求的人，因此他希望他的画从左往右是越来越美观的，即对于任意两个画了图案的格子$l < r$，有$a_l \leqslant a_r$
但蒜头发现，人们评判画卷的好坏，并不会只从画出的图案来考虑
具体来说，一张画卷的美观度，定义为所有画了图案的位置的美观度之和与在图上选择两个可以重复的位置使得两位置之间不存在画了图案的位置的方案数之差
现在，蒜头想要知道，他画出的画卷的最大美观度是多少
形式化地，一段连续的长度为$m$的空白位置会让美观度降低$\frac{m(m+1)}{2}$
输入格式
输入的第一行是一个数$n$，表示序列的长度
接下来一行$n$个数，第$i$个数表示$a_i$
输出格式
输出一行表示最大美观度
样例
样例输入
输入样例1
1 | 7 |
输入样例2
1 | 7 |
样例输出
输出样例1
1 | 7 |
输出样例2
1 | -11 |
数据范围与提示
对于$100 \%$的数据，$-10^8 \leqslant a_i \leqslant 10^8$
对于子任务$1$，$19$分，$n \leqslant 20$
对于子任务$2$，$22$分，$n \leqslant 5000$
对于子任务$3$，$18$分， $n \leqslant 10^6$，数据随机
对于子任务$4$，$41$分，$n \leqslant 10^6$
题解
首先，我们先不考虑“对于任意两个画了图案的格子$l1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
using namespace std;
int n,q[1000010],a[1000010],ord[1000010],rk[21][1000010];
long long ans,f[1000010];
int cmp(const int &x,const int &y)
{
return a[x]<a[y]||(a[x]==a[y]&&x<y);
}
long long Slope(int x)
{
return 2*f[x]-1ll*x*x-x;
}
void Merge_Sort(int l,int r,int d)
{
if(l==r){rk[d][l]=ord[l];return;}
int mid=(l+r)>>1;
Merge_Sort(l,mid,d+1),Merge_Sort(mid+1,r,d+1);
int i=l,j=mid+1,rank=l-1;
while(i<=mid&&j<=r){
if(rk[d+1][i]<rk[d+1][j]) rk[d][++rank]=rk[d+1][i++];
else rk[d][++rank]=rk[d+1][j++];
}
while(i<=mid) rk[d][++rank]=rk[d+1][i++];
while(j<=r) rk[d][++rank]=rk[d+1][j++];
}
void CDQ_DC(int l,int r,int d)
{
if(l==r){
f[ord[l]]=max(f[ord[l]],a[ord[l]]-1ll*(ord[l]-1)*ord[l]/2);
ans=max(ans,f[ord[l]]-1ll*(n-ord[l])*(n-ord[l]+1)/2);
return;
}
int mid=(l+r)>>1,H=1,T=0;
CDQ_DC(l,mid,d+1),q[H]=q[T]=0;
for(int i=mid+1,k=l;i<=r;i++){
int j=rk[d][i];
while(k<=mid&&rk[d][k]<j){
long long w=rk[d][k];
while(H<T&&((Slope(w)-Slope(q[T]))*(q[T]-q[T-1])>=(Slope(q[T])-Slope(q[T-1]))*(w-q[T]))) T--;
q[++T]=w,k++;
}
while(H<T&&(Slope(q[H+1])-Slope(q[H])>=-2ll*j*(q[H+1]-q[H]))) H++;
if(H<=T&&H) f[j]=max(f[j],f[q[H]]+a[j]-1ll*(j-q[H]-1)*(j-q[H])/2);
ans=max(ans,f[j]-1ll*(n-j)*(n-j+1)/2);
}
CDQ_DC(mid+1,r,d+1);
}
int main()
{
freopen("paint.in","r",stdin);
freopen("paint.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]),ord[i]=i,f[i]=-1e18;
sort(ord+1,ord+n+1,cmp),ans=-1ll*n*(n+1)/2,Merge_Sort(1,n,0),CDQ_DC(1,n,1),printf("%lld",ans);
}