https://www.luogu.org/problemnew/show/P2048
http://www.lydsy.com/JudgeOnline/problem.php?id=2006
首先计算出数列的前缀和数组a[0]..a[n]，那么问题转化为：从[0,n]中选取任意两个数(i,j)使得i<j，计算a[j]-a[i]；对于所有合法的数对(i,j)，求第k大的a[j]-a[i]的值。
考虑枚举i，对于每一个i要得到第k大的a[j]-a[i]，则需要从[i+1,n]中选取j使得a[j]是a[i+1]到a[n]中第k大的。
用一个优先队列维护一下，然后问题就只剩区间k大了。可以用静态主席树搞一下。
但是你会发现T到飞起...常数太大了2333333
本来动态开点偷懒都不行了
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector")
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
#pragma GCC diagnostic error "-std=c++14"
#include<cstdio>
#include<algorithm>
#include<queue>
#include<tr1/unordered_map>
#define mid ((l+r)>>1)
using namespace std;
typedef long long LL;
typedef pair<LL,int> P;
tr1::unordered_map<LL,int> ma;
LL tmp[],ma2[];
int mem,lc[],rc[],dat[],root[];
LL ll,rr,totn;
LL L;int x;
//root[i]表示[i+L,i+R]区间的线段树，也就是选i+1号为左端点时右端点可取范围
void addx(LL l,LL r,int& num)
{
int t=num;num=++mem;//if(mem>=40000000){puts("test");exit(0);}
lc[num]=lc[t];rc[num]=rc[t];dat[num]=dat[t];
if(l==r) {dat[num]+=x;return;}
if(L<=mid) addx(l,mid,lc[num]);
else addx(mid+,r,rc[num]);
dat[num]=dat[lc[num]]+dat[rc[num]];
}
LL getx(LL l,LL r,int num)//第x大
{
if(l==r) return l;
if(dat[rc[num]]>=x) return getx(mid+,r,rc[num]);
else return x-=dat[rc[num]],getx(l,mid,lc[num]);
}
int n,k,lx,rx;LL ans;
LL a[];int nownum[];
priority_queue<P> q;
//P(当前和，i)(当前和等于[i+L,i+R]的第nownum[i]大-a[i])
//void out(LL l,LL r,LL num)
//{
// if(l==r) {for(LL i=1;i<=dat[num];i++) printf("%lld ",l);return;}
// out(l,mid,lc[num]);out(mid+1,r,rc[num]);
//}
//void out()
//{
// queue<P> qq;P t;
// while(!q.empty()) {t=q.top();q.pop();printf("%lld %lld\n",t.first,t.second);qq.push(t);}
// while(!qq.empty()) {t=qq.front();qq.pop();q.push(t);}
//}
int main()
{
int l=,r=-,i;P t;
scanf("%d%d%d%d",&n,&k,&lx,&rx);
for(i=;i<=n;i++) scanf("%lld",&a[i]),a[i]+=a[i-],tmp[++tmp[]]=a[i];
sort(tmp+,tmp+tmp[]+);totn=unique(tmp+,tmp+tmp[]+)-tmp-;
for(i=;i<=totn;i++) ma[tmp[i]]=i,ma2[i]=tmp[i];
for(i=;i<=n;i++) a[i]=ma[a[i]];
ll=;rr=totn;
while(r<n&&r<rx) r++,L=a[r],x=,addx(ll,rr,root[]);
while(l<=n&&l<lx) L=a[l],x=-,addx(ll,rr,root[]),l++;
if(l<=r)
{
x=nownum[]=;
q.push(P(ma2[getx(ll,rr,root[])]-ma2[a[]],));
}
for(i=;i<n;i++)
{
root[i]=root[i-];
while(r<n&&r<i+rx) r++,L=a[r],x=,addx(ll,rr,root[i]);
while(l<=n&&l<i+lx) L=a[l],x=-,addx(ll,rr,root[i]),l++;
if(l<=r)
{
x=nownum[i]=;
q.push(P(ma2[getx(ll,rr,root[i])]-ma2[a[i]],i));
}
}
//out();
//printf("\n%lld",mem);
//return 0;
for(i=;i<=k;i++)
{
t=q.top();q.pop();
//printf("a%lld\n",t.first);
ans+=t.first;
++nownum[t.second];
//l=min(n+1,t.second+lx);r=min(n,t.second+rx);
//if(r-l+1<nownum[t.second]) continue;
if(dat[root[t.second]]<nownum[t.second]) continue;
x=nownum[t.second];
q.push(P(ma2[getx(ll,rr,root[t.second])]-ma2[a[t.second]],t.second));
}
printf("%lld",ans);
//for(i=0;i<n;i++) {out(ll,rr,root[i]);puts("");}
return ;
}错误记录：90行写成dat[t.second]；动态开点（没有离散化）时误以为值域只有-1000到1000（但事实上值域是前缀和的值域，-5e8到5e8）
开了奇怪的Ofast后A掉了....
其实有更优越的做法，就是维护优先队列时，每次搞完[l,r]区间最大值（在k位置）后，就把它拆成[l,k-1]和[r+1,k]（还有这两个区间内分别的最小值）分别放回去，这样恰好去掉了之前的最大值，又不破坏次大值、第三大值、....。这样只需要ST表预处理一下然后RMQ就行了，好写&常数小
这里有一个一模一样的题，并过来