2018.12.28-bzoj-2006-[NOI2010]超级钢琴

#include<bits/stdc++.h>
#define il inline
#define _(d) while(d(isdigit(ch=getchar())))
using namespace std;
const int N=5e5+5;
struct node{int x,l,r,pos,v;friend bool operator<(node t1,node t2) {return t1.v<t2.v;}};
int n,k,L,R,sum[N],mx[N][20],Log[N];long long ans;priority_queue<node> q;
il int read(){int x,f=1;char ch;_(!)ch==‘-‘?f=-1:f;x=ch^48;_()x=(x<<1)+(x<<3)+(ch^48);return f*x;}
il int Max(int x,int y){return sum[x]<sum[y]?y:x;}
il int query(int l,int r){int k=Log[r-l+1];return Max(mx[l][k],mx[r-(1<<k)+1][k]);}
int main()
{
    n=read();k=read();L=read();R=read();
    for(int i=1;i<=n;i++)sum[i]=sum[i-1]+read(),mx[i][0]=i;
    for(int i=2;i<=n;i++)Log[i]=Log[i>>1]+1;
    for(int j=1;j<=Log[n];j++)for(int i=1;i+(1<<j-1)<=n;i++)
        mx[i][j]=Max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);
    for(int i=1;i+L-1<=n;i++){
        int pos=query(i+L-1,min(i+R-1,n));q.push((node){i,i+L-1,min(i+R-1,n),pos,sum[pos]-sum[i-1]});
    }
    while(k--){
        node now=q.top();q.pop();ans+=now.v;int p;
        if(now.l<now.pos)p=query(now.l,now.pos-1),q.push((node){now.x,now.l,now.pos-1,p,sum[p]-sum[now.x-1]});
        if(now.pos<now.r)p=query(now.pos+1,now.r),q.push((node){now.x,now.pos+1,now.r,p,sum[p]-sum[now.x-1]});
    }
    printf("%lld\n",ans);
    return 0;
}