P5892 题解

前言

这是蒟蒻的第四篇题解哦
顺便也是第一道独立切的决策单调性呢～
一看题解区好像都是写分治的，然鹅蒟蒻不会分治，于是来写了篇二分栈 orz

思路

显然，我们不能走冤枉路，故而一定是向一个方向走一段路，再往反方向走一段，由于问题的对称性，以下默认先往左走，另一个方向翻转一下即可。
如此，任意下标 $i\ (s\leq i< n)\$ 都可以从下标 $j\ (0\leq j\leq s)\$ 转移，表示先从 $s$ 走到 $j$，再走到 $i$，并终止旅程。
设 $sum_{l,r}[k]$ 为子数组 $a[l...r]$ 中最大的 $k$ 个元素之和，有状态转移方程：

朴素转移太慢，于是可以直接猜个决策单调性，感性理解一下，既然我们在右边花了更多时间赶路，那么便没理由在左边花那么多时间。
因为 $sum$ 可以通过主席树 $O(\log n)$ 查询，结合上二分栈和循环的复杂度，最终复杂度是 $O(n\log^2n)$。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1<<17;
ll ans;
int n,m,s,d,tot;
int a[N],id[N],rt[N];
struct sgt{int l,r,ch[2],sz;ll sum;} t[N<<5];
int node(int l,int r){return t[++tot]={l,r,0,0,0,0},tot;}
int copy(int x){return t[++tot]=t[x],tot;}
void up(int x){t[x].sz=t[t[x].ch[0]].sz+t[t[x].ch[1]].sz,t[x].sum=t[t[x].ch[0]].sum+t[t[x].ch[1]].sum;}
void modify(int u,int &x,int y,int l=1,int r=m){
	if(l>u||r<u) return;
	x=y?copy(y):node(l,r);
	int mid=(l+r)>>1;
	if(l==r) t[x].sz++,t[x].sum+=id[u];
	else modify(u,t[x].ch[0],t[y].ch[0],l,mid),modify(u,t[x].ch[1],t[y].ch[1],mid+1,r),up(x);
}
ll query(int k,int x,int y){
	if(k<=0||!(t[y].sum-t[x].sum)) return 0;
	if(t[y].sz-t[x].sz<=k) return t[y].sum-t[x].sum;
	if(t[y].l==t[y].r) return 1ll*id[t[y].l]*k;
	return query(k-(t[t[y].ch[1]].sz-t[t[x].ch[1]].sz),t[x].ch[0],t[y].ch[0])+query(k,t[x].ch[1],t[y].ch[1]);
}
int tp;
array<int,3> st[N];
ll w(int j,int i){return query(d-(s-j)*2-(i-s),rt[j-1],rt[i]);}
void solve(){
	for(int i=1;i<=tot;i++) t[i]={0,0,0,0,0,0};
	reverse(a+1,a+n+1),s=n-s+1,tp=0,tot=0;
	for(int i=1;i<=n;i++) modify(a[i],rt[i],rt[i-1]);
	for(int i=1;i<=s;i++){
		while(tp&&w(st[tp][0],st[tp][1])<=w(i,st[tp][1])) tp--;
		if(tp){
			int l=st[tp][1]+1,r=st[tp][2],k=r+1;
			while(l<=r){
				int mid=(l+r)>>1;
				if(w(st[tp][0],mid)<=w(i,mid)) k=mid,r=mid-1;
				else l=mid+1;
			}
			st[tp][2]=k-1;
			if(k<=n) st[++tp]={i,k,n};
		}else st[++tp]={i,s,n};
	}
	for(;tp;tp--) for(int i=st[tp][1];i<=st[tp][2];i++) ans=max(ans,w(st[tp][0],i));
}
int main(){
	scanf("%d%d%d",&n,&s,&d),s++;
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),id[i]=a[i];
	sort(id+1,id+n+1),m=unique(id+1,id+n+1)-id-1;
	for(int i=1;i<=n;i++) a[i]=lower_bound(id+1,id+m+1,a[i])-id;
	solve(),solve(),printf("%lld",ans);
	return 0;
}