[NOI2010] 超级钢琴

这也算是第K大问题的套路题了（虽然我一开始还想了个假算法），大体想法就是先弄出最优的一批解，然后每次从中提出一个最优解并转移到一个次优解，用优先队列维护这个过程即可。

类似的问题很多，放在序列上的，放在图上的，改天可以考虑补个专题。

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 1000005;

int a[N],s[N],st[N][20],stp[N][20],n,k,L,R;

int query(int l,int r)
{
    int lg=log2(r-l+1);
    int tmp = max(st[l][lg],st[r-(1<<lg)+1][lg]);
    if(tmp==st[l][lg]) return stp[l][lg];
    else return stp[r-(1<<lg)+1][lg];
}

inline int eval(int o,int l,int r)
{
    return s[query(l,r)]-s[o-1];
}

struct Item
{
    int o,l,r;
    bool operator < (const Item &b) const
    {
        return eval(o,l,r) < eval(b.o,b.l,b.r);
    }
};

Item gen(int o,int l,int r)
{
    Item tmp;
    tmp.o=o;
    tmp.l=l;
    tmp.r=r;
    return tmp;
}

priority_queue <Item> q;
int ans = 0;

signed main()
{
    cin>>n>>k>>L>>R;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        s[i]=s[i-1]+a[i];
        st[i][0]=s[i];
        stp[i][0]=i;
    }
    for(int j=1;j<=19;j++)
        for(int i=1;i+(1<<j)-1<=n;i++)
        {
            st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
            if(st[i][j]==st[i][j-1])
                stp[i][j]=stp[i][j-1];
            else
                stp[i][j]=stp[i+(1<<(j-1))][j-1];
        }
    for(int i=1;i+L-1<=n;i++)
    {
        q.push(gen(i,i+L-1,min(i+R-1,n)));
    }
    while(k--)
    {
        Item p=q.top();
        q.pop();
        int tans = eval(p.o,p.l,p.r);
        ans += tans;
        int mid = query(p.l,p.r);
        if(mid!=p.l)
        {
            Item x=p;
            x.r=mid-1;
            if(x.r>=x.l) q.push(x);
        }
        if(mid!=p.r)
        {
            Item x=p;
            x.l=mid+1;
            if(x.r>=x.l) q.push(x);
        }
    }
    cout<<ans<<endl;
}