正题
题目链接:http://noi.ac/problem/2139
题目大意
给出\(n\)个数字的序列\(a_i\)。然后选出一个不降子序列最大化子序列的\(a_i\)和减去没有任何一个数被选中的区间数量。
\(1\leq n\leq 10^6,1\leq a_i\leq 10^8\)
解题思路
嗯，考虑朴素的\(dp\)方程，设\(f_i\)表示以\(i\)为末尾的值就有
\[f_i=f_j+a_i+\frac{(i-j-1)(i-j)}{2}
\]
然后展开整理一下都乘二就是
\[f_i=f_j+2a_i+i^2-i+j^2+j-2ij(a_j\leq a_i,j<i)
\]
除了\(a_j\leq a_i\)就是一个标准的斜率优化式子了
然后这个东西其实挺好搞的，因为多一个限制直接上\(CDQ\)就好了，但是每次左边要归并排序，这样时间复杂度就是\(O(n\log n)\)的了
但其实还有更暴力的做法，因为既然一个\(CDQ\)能做到，那么找些数据结构之类的也肯定能做到。
对于树状数组上每个节点维护一个凸壳然后暴力查询就好了
时间复杂度\(O(n\log n)\)
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ll long long
#define lowbit(x) (x&-x)
using namespace std;
const ll N=1e6+10;
ll n,m,a[N],b[N],l[N],r[N],f[N],k[N];
vector<ll >q[N];
ll calc(ll i,ll j)
{return k[i]+2*i*j;}
void Change(ll x,ll i){
while(x<=m){
while(l[x]<r[x]&&(k[i]-k[q[x][r[x]]])*(q[x][r[x]]-q[x][r[x]-1])>=(k[q[x][r[x]]]-k[q[x][r[x]-1]])*(i-q[x][r[x]]))
r[x]--,q[x].pop_back();
q[x].push_back(i);r[x]++;x+=lowbit(x);
}
return;
}
ll Ask(ll x,ll i){
ll ans=-1e18;
while(x){
while(l[x]<r[x]&&calc(q[x][l[x]],i)<calc(q[x][l[x]+1],i))
l[x]++;
if(l[x]<=r[x])ans=max(ans,calc(q[x][l[x]],i));
x-=lowbit(x);
}
return ans;
}
signed main()
{
scanf("%lld",&n);
for(ll i=1;i<=n;i++)
scanf("%lld",&a[i]),b[i]=a[i];
sort(b+1,b+1+n);
m=unique(b+1,b+1+n)-b-1;
for(ll i=1;i<=m;i++)r[i]=-1;
Change(1,0);
for(ll i=1;i<=n;i++){
ll x=lower_bound(b+1,b+1+m,a[i])-b;
f[i]=Ask(x,i)+2*a[i]-i*i+i;
k[i]=f[i]-i*i-i;
Change(x,i);
}
ll ans=-1e18;
for(ll i=1;i<=n;i++)
ans=max(ans,f[i]/2-(n-i+1)*(n-i)/2);
printf("%lld\n",ans);
return 0;
}