题目

小 Z 是一个小有名气的钢琴家，最近 C 博士送给了小 Z 一架超级钢琴，小 Z 希望能够用这架钢琴创作出世界上最美妙的音乐。

这架超级钢琴可以弹奏出 nn 个音符，编号为 11 至 nn。第 ii 个音符的美妙度为 A_iA
i
​
，其中 A_iA
i
​
可正可负。

一个“超级和弦”由若干个编号连续的音符组成，包含的音符个数不少于 LL 且不多于 RR。我们定义超级和弦的美妙度为其包含的所有音符的美妙度之和。两个超级和弦被认为是相同的，当且仅当这两个超级和弦所包含的音符集合是相同的。

小 Z 决定创作一首由 kk 个超级和弦组成的乐曲，为了使得乐曲更加动听，小 Z 要求该乐曲由 kk 个不同的超级和弦组成。我们定义一首乐曲的美妙度为其所包含的所有超级和弦的美妙度之和。小 Z 想知道他能够创作出来的乐曲美妙度最大值是多少。

思路

这道题简单来说，就是给你一个序列a，求前k大长度在(l,r)内的子串和
显然n^2可以做（T飞）

先找到最大值，然后删掉最大值，继续找剩下值中的最大值就可以了

假设现在我们一个区间都没删，现在要找最大值，

那么我们枚举左端点l，然后考虑对于一个给定的左端点l哪个是最优的右端点r 因为长度限制是[l,r]因此对于这个l来讲，所有合法的右端点r形成一个区间

当然是一个区间的前缀和值的最大值所对应的r了，因为总之你都要减去左端点的前缀和……，因此当然是要r的前缀和最大咯

这是一个区间最大值问题，当然可以使用st表解决这个问题

但是如果使用主席树解决这个静态区间第k大问题也不是不可以对吧……

然后我们对于每一个左端点都求出了一个最大合法的子串和

所以把这些值放进堆里取就可以找到最大值，好了我们现在有了一个最大值！

现在我们取出了这个最大值……我们发现此时这个左端点对应的区间第2大可能是此时最大的值，因此我们再求一遍区间第2大插堆里去，同理如果我们取出来来了区间第2大就插区间第3大，当然如果取掉了区间最小值就不能插入了……

代码

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+77;
struct node
{int num,lid,rid,w,data;bool operator <(node i)const{return data<i.data;}
};
int c[N],dp[N][20],lg[N],num[N][20],p[N],n,k,l,r,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];elsejl=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);}printf("%lld",ans);
}