超级钢琴（主席树+贪心+优先队列）

超级钢琴

我能说这是主席树板子题嘛？

题意：给定一个序列，求长度在 $L$L与 $R$R内的前 $K$K大子串和。

思路：

1. 既然有子串，肯定要先搞个前缀和，离散化之类的
2. 然后我们建好主席树
3. 而主要的思路在于贪心，我们可以枚举子串的左端点，然后在其合法的右端点中通过主席树找到最大的右端点（子串满足前缀和关系，每个右端点都会减去这个相同的左端点的前一个值）
4. 把枚举得到的所有最大子串都放进优先队列中（维护左端点+最大子串），每次取出队头，就在答案中加上这个值，然后再以当前左端点利用主席树求区间第 $j+1$j+1大（假设刚刚取出的是第 $j$j大），又塞进优先队列即可
5. 这样时间复杂度应该是 $O(k\ast logn)$O(k∗logn)，优先队列的空间复杂度为 $O(n+k)$O(n+k)

题面描述

#include "bits/stdc++.h"
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0,f=1;char c=getchar();while(c!='-'&&(c<'0'||c>'9'))c=getchar();if(c=='-')f=-1,c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return f*x;}

const int maxn = 5e5+10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const double eps = 1e-7;

int n, nn, K, L, R;
int a[maxn], b[maxn];
int root[maxn], ls[maxn<<5], rs[maxn<<5];
int sz[maxn<<5], sum[maxn<<5], tot;

void update(int x, int l, int r, int pre, int &now) {
    now=++tot;
    ls[now]=ls[pre], rs[now]=rs[pre], sz[now]=sz[pre]+1;
    if(l==r) return;
    int m=(l+r)/2;
    if(x<=m) update(x,l,m,ls[pre],ls[now]);
    else update(x,m+1,r,rs[pre],rs[now]);
}

int qk(int k, int x, int y, int l, int r) {
    if(l==r) return b[l];
    int s0=sz[y]-sz[x];
    if(k>s0) return -inf;
    int s=sz[rs[y]]-sz[rs[x]], m=(l+r)/2;
    if(s>=k) return qk(k,rs[x],rs[y],m+1,r);
    else return qk(k-s,ls[x],ls[y],l,m);
}

struct P{
    int st, v;
    bool operator < (const P &rhs) const {
        return v<rhs.v;
    }
};

int mxk[maxn];
priority_queue<P> q;

int main() {
    //ios::sync_with_stdio(false); cin.tie(0);
    n=read(), K=read(), L=read(), R=read();
    for(int i=1; i<=n; ++i) b[i]=a[i]=a[i-1]+read();
    sort(b+1,b+1+n); nn=unique(b+1,b+1+n)-b-1;
    for(int i=1; i<=n; ++i) a[i]=lower_bound(b+1,b+1+nn,a[i])-b;
    for(int i=1; i<=n; ++i) update(a[i],1,nn,root[i-1],root[i]);
    for(int i=1; i<=n-L+1; ++i) q.push((P){i,qk(++mxk[i],root[i+L-2],root[min(n,i+R-1)],1,nn)-b[a[i-1]]});
    int cnt=0; ll ans=0;
    while(1) {
        P now=q.top(); q.pop();
        ans+=now.v; if(++cnt==K) break;
        q.push((P){now.st,qk(++mxk[now.st],root[now.st+L-2],root[min(n,now.st+R-1)],1,nn)-b[a[now.st-1]]});
    }
    printf("%lld\n", ans);
}