P2048

good rmq

#include<bits/stdc++.h>
using namespace std;
struct node {
	int num;
	int lid,rid;
	int w;
	int data;
	bool operator <(node i)const {
		return data<i.data;
	}
};
int c[500005],dp[500005][20],lg[500005];
int num[500005][20];
int p[500005];
int n,k,l,r;
int minn=2147483647;
long long ans=0;
priority_queue<node>q;
void RMQ() {
	for(int j=1; j<=20; j++) {
		for(int i=1; i<=n; i++) {
			if(i+(1<<j)-1<=n) {
				if(dp[i][j-1]<dp[i+(1<<(j-1))][j-1]) {
					dp[i][j]=dp[i+(1<<(j-1))][j-1];
					num[i][j]=num[i+(1<<(j-1))][j-1];
				} else {
					dp[i][j]=dp[i][j-1];
					num[i][j]=num[i][j-1];
				}
			}
		}
	}
}
int wz(int x,int y) {
	int tmp=lg[y-x+1];
	int o,jl;
	if(dp[x][tmp]>dp[y-(1<<tmp)+1][tmp])
		jl=num[x][tmp];
	else
		jl=num[y-(1<<tmp)+1][tmp];
	return jl;
}
void add(int po,int i,int left,int right) {
	node tmp;
	tmp.w=po;
	tmp.num=i;
	tmp.lid=left;
	tmp.rid=right;
	tmp.data=c[po]-c[i-1];
	q.push(tmp);
	return ;
}
int main() {
	cin>>n>>k>>l>>r;
	lg[0]=-1;
	for(int i=1; i<=n; i++) {
		int x;
		cin>>x;
		c[i]=c[i-1]+x;
		dp[i][0]=c[i];
		num[i][0]=i;
		lg[i]=lg[i/2]+1;
	}
	RMQ();
	for(int i=1; i+l-1<=n; i++)add(wz(i+l-1,min(i+r-1,n)),i,i+l-1,min(i+r-1,n));
	while(k--) {
		int d=q.top().w,left=q.top().lid,right=q.top().rid;
		int e=q.top().data,id=q.top().num;
		ans+=e;
		q.pop();
		if(d>left)add(wz(left,d-1),id,left,d-1);
		if(d<right)add(wz(d+1,right),id,d+1,right);
	}
	cout<<ans<<endl;
	return 0;
}