https://blog.csdn.net/CreationAugust/article/details/50821931
当需要枚举的东西呈单调性的时候可以用分治解决。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rep(i,l,r) for (int i=l; i<=r; i++)
typedef long long ll;
using namespace std; const int N=,M=;
int n,st,m,cnt,root[N],b[N],sta[N],c,ls[M],rs[M],sz[M];
ll ret,ans,sum[M],f[N],g[N],f1[N],g1[N];
int fd[N],gd[N],f1d[N],g1d[N]; void ins(int x,int &y,int l,int r,int val,ll Val){
sz[y=++cnt]=sz[x]+; sum[y]=sum[x]+Val; ls[y]=ls[x];rs[y]=rs[x];
if (l==r) return; int mid=(l+r)>>;
if (val<=mid) ins(ls[x],ls[y],l,mid,val,Val);
else ins(rs[x],rs[y],mid+,r,val,Val);
} void query(int x,int y,int l,int r,int k){
if (k<=) return;
if (l==r) { ret+=1ll*min(k,sz[y]-sz[x])*sta[l]; return; }
int mid=(l+r)>>;
if (sz[rs[y]]-sz[rs[x]]>=k) query(rs[x],rs[y],mid+,r,k);
else ret+=sum[rs[y]]-sum[rs[x]],query(ls[x],ls[y],l,mid,k-sz[rs[y]]+sz[rs[x]]);
} void solve1(int l,int r,int L,int R){//要求f[l..r],d的范围在[L,R]
if (l>r) return;
int mid=(l+r)>>;
for (int i=L;i<=R;i++){
ret=; query(root[st-],root[i],,c,st-i+mid);
if (ret>f[mid]||!fd[mid]) f[mid]=ret,fd[mid]=i;
}
solve1(l,mid-,L,fd[mid]);solve1(mid+,r,fd[mid],R);
} void solve2(int l,int r,int L,int R){
if (l>r) return;
int mid=(l+r)>>;
for (int i=R; i>=L; i--){
ret=; query(root[i-],root[st-],,c,i-st+mid);
if (ret>g[mid]||!gd[mid]) g[mid]=ret,gd[mid]=i;
}
solve2(l,mid-,gd[mid],R); solve2(mid+,r,L,gd[mid]);
} void solve3(int l,int r,int L,int R){
if (l>r) return;
int mid=(l+r)>>;
for (int i=L; i<=R; i++){
ret=; query(root[st-],root[i],,c,((st-i)<<)+mid);
if (ret>f1[mid]||!f1d[mid]) f1[mid]=ret,f1d[mid]=i;
}
solve3(l,mid-,L,f1d[mid]); solve3(mid+,r,f1d[mid],R);
} void solve4(int l,int r,int L,int R){
if (l>r) return;
int mid=(l+r)>>;
for (int i=R;i>=L;i--){
ret=; query(root[i-],root[st-],,c,((i-st)<<)+mid);
if (ret>g1[mid]||!g1d[mid]) g1[mid]=ret,g1d[mid]=i;
}
solve4(l,mid-,g1d[mid],R);solve4(mid+,r,L,g1d[mid]);
} int main(){
freopen("bzoj4367.in","r",stdin);
freopen("bzoj4367.out","w",stdout);
scanf("%d%d%d",&n,&st,&m);st++;
rep(i,,n) scanf("%d",&b[i]),sta[i]=b[i];
sort(sta+,sta+n+);c=unique(sta+,sta+n+)-sta-;
rep(i,,n) b[i]=lower_bound(sta+,sta+c+,b[i])-sta;
rep(i,,n) ins(root[i-],root[i],,c,b[i],sta[b[i]]);
solve1(,m,st,min(n,st+m)); solve2(,m,max(,st-m),n);
solve3(,m,st,min(n,st+(m>>))); solve4(,m,max(,st-(m>>)),n);
rep(i,,m) ans=max(ans,g1[i]+f[m-i]);
rep(i,,m) ans=max(ans,f1[i]+g[m-i]);
printf("%lld\n",ans);
}