题目
题解

Solution

对于任意区间右端点 i i i，其左端点取值在 l l l, r r r之间，若左端点为 m m m，则 v v v为 m a x ( s u m [ i ] − s u m [ m − 1 ] ) max(sum[i]-sum[m-1]) max(sum[i]−sum[m−1])，显然这里 i i i是不变的，所以可以用 s t st st表查询 m m m的位置，然后计算v。
现将所有右端点扫一遍，然后扔到堆里面，堆中节点记录的是决策，即右端点 i i i，左端点区间，优先级由 v v v决定
然后取出堆顶， v v v加到 a n s ans ans里去，分裂 [ l , r ] [l,r] [l,r]为 [ l , m − 1 ] [l,m-1] [l,m−1]和 [ m + 1 , r ] [m+1,r] [m+1,r]， R M Q RMQ RMQ出新的 v v v，再将分裂后的区间加到堆里
重复 k k k次

Code

#include<bits/stdc++.h>
using namespace std;
const int N=500002;
struct node{
	int i,l,m,r,v;
	friend bool operator <(node a,node b){return a.v<b.v;}
}t;
priority_queue<node>q;
int lg[N],L,R,i,j,n,k,a[N],tmp,st[N][20],l,r,m;
long long ans;
inline char gc(){
	static char buf[100000],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int rd(){
	int x=0,fl=1;char ch=gc();
	for (;ch<48||ch>57;ch=gc())if(ch=='-')fl=-1;
	for (;48<=ch&&ch<=57;ch=gc())x=(x<<3)+(x<<1)+(ch^48);
	return x*fl;
}
int get(int x,int y){
	x--;y--;
	int l=lg[y-x+1];
	if (a[st[x][l]]<a[st[y-(1<<l)+1][l]]) return st[x][l]+1;
	return st[y-(1<<l)+1][l]+1;
}
int main(){
	n=rd();k=rd();L=rd();R=rd();
	lg[0]=-1;
	for (i=1;i<=n;i++) a[i]=rd()+a[i-1],lg[i]=lg[i>>1]+1,st[i][0]=i;
	for (j=1;j<=lg[n];j++)
		for (i=0;i+(1<<j)-1<=n;i++)
			if (a[st[i][j-1]]<a[st[i+(1<<j-1)][j-1]]) st[i][j]=st[i][j-1];
			else st[i][j]=st[i+(1<<j-1)][j-1];
	for (i=1;i<=n;i++){
		l=max(i-R+1,1);r=max(i-L+1,1);
		if (i-l+1<L) continue;
		m=get(l,r);
		q.push((node){i,l,m,r,a[i]-a[m-1]});
	}
	while (k--){
		t=q.top();q.pop();
		ans+=t.v;
		l=t.l;r=t.r;m=t.m;
		if (l<m){
			tmp=get(l,m-1);
			q.push((node){t.i,l,tmp,m-1,a[t.i]-a[tmp-1]});
		}
		if (m<r){
			tmp=get(m+1,r);
			q.push((node){t.i,m+1,tmp,r,a[t.i]-a[tmp-1]});
		}
	}
	printf("%lld",ans);
}