学步园

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2006

在堆里维护每个以i为左端点的区间,取出来一个区间[i,j]后,再加入[l,j-1]的max和[j+1,r]的max,l,r是指i向右可控制的范围

Code:

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+10;
typedef pair<int,int> pii;
int n,k,L,R;
int a[maxn],sum[maxn];
int f[20][maxn],g[20][maxn];
long long ans=0;
void ST_init(){
	int BIT=0;
	for(int i=n;i;i>>=1,BIT++);
	for(int i=1;i<=n;i++)f[0][i]=sum[i],g[0][i]=i;
	for(int i=1;i<=BIT;i++)
	for(int j=1;j<=n-(1<<i)+1;j++){
		if(f[i-1][j]>f[i-1][j+(1<<i-1)])
			f[i][j]=f[i-1][j],g[i][j]=g[i-1][j];
		else f[i][j]=f[i-1][j+(1<<i-1)],g[i][j]=g[i-1][j+(1<<i-1)];
	}
}
pii qmax(int l,int r){
	int BIT=0;
	for(int i=r-l+1;i;i>>=1,BIT++);BIT--;
 	if(f[BIT][l]>f[BIT][r-(1<<BIT)+1])return pii(g[BIT][l],f[BIT][l]);  
    else return pii(g[BIT][r-(1<<BIT)+1],f[BIT][r-(1<<BIT)+1]);  	
}
struct zky{
	int i,j,l,r,v;
	zky(int i=0,int j=0,int l=0,int r=0,int v=0):
		i(i),j(j),l(l),r(r),v(v){}
	bool operator<(const zky &sb)const{
		return v<sb.v;
	}
};
priority_queue<zky>q;
int main(){
	scanf("%d%d%d%d",&n,&k,&L,&R);
	for(int i=1;i<=n;i++)scanf("%d",a+i),sum[i]=sum[i-1]+a[i];
	ST_init();
	for(int i=1;i<=n;i++){
		if(i-1+L>n)break;  
		pii x=qmax(i+L-1,min(i+R-1,n));
		q.push(zky(i,x.first,i-1+L,min(i+R-1,n),x.second-sum[i-1]));  
	}
	while(k--){
		zky x=q.top();q.pop();
		ans+=x.v;
		if(x.j-1>=x.l){
			pii t=qmax(x.l,x.j-1);
			q.push(zky(x.i,t.first,x.l,x.j-1,t.second-sum[x.i-1])); 
		}
		if(x.j+1<=x.r){
	        pii t=qmax(x.j+1,x.r);  
            q.push(zky(x.i,t.first,x.j+1,x.r,t.second-sum[x.i-1]));  		
		}
	}cout<<ans<<endl;
	return 0;
}