分析
堆+主席树。
考虑对于每个左端点 $l$ ,先找到一个 $r$ 使得 $\sum\limits_{i=l}^ra[i]$ 最大。
设 $s[i]=\sum\limits_{j=1}^i a[i]$ ,也就是说要找到一个 $r$ 使得 $sum[r]-sum[l-1]$ 最大。
显然只要在 $r$ 的范围内找区间最大值就行了,因为 $sum[l-1]$ 是定值。
这样子就找到了一些和弦,把这些和弦丢到一个以美妙度为关键字的大根堆里去。
那么我们取出堆顶,这样就有了一个最大值。那么下一个可能成为最大值的有所有堆中的元素,以及这个最大值对应的左端点对应的区间的第 $2$ 大值。
于是重复这个过程,每次取出堆顶(假设是第 $k$ 大值),然后把对应的第 $k+1$ 大值丢进去。当已经是最小值的时候就不用丢了。
把这个过程进行 $k$ 遍就求出了答案。
至于怎么查第 $k$ 大,拿个主席树维护一下就行了。
细节比较多。具体实现及细节见代码。
代码
// =================================
// author: M_sea
// website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
typedef long long ll;
using namespace std;
inline int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}
const int N=500000+10;
int a[N],s[N],S[N],rt[N];
struct node { int p,cnt,val; };
bool operator <(node a,node b) { return a.val<b.val; }
priority_queue<node> Q;
struct President_Tree {
struct node { int ls,rs,sum; } t[N*30];
int tot;
President_Tree() { tot=0; }
inline void modify(int& p,int q,int l,int r,int pos,int w) {
t[p=++tot]=t[q];
if (l==r) { t[p].sum+=w; return; }
int mid=(l+r)>>1;
if (pos<=mid) modify(t[p].ls,t[q].ls,l,mid,pos,w);
else modify(t[p].rs,t[q].rs,mid+1,r,pos,w);
t[p].sum=t[t[p].ls].sum+t[t[p].rs].sum;
}
inline int query(int p,int q,int l,int r,int k) {
if (l==r) return l;
int mid=(l+r)>>1,rsum=t[t[q].rs].sum-t[t[p].rs].sum;
if (rsum>=k) return query(t[p].rs,t[q].rs,mid+1,r,k);
else return query(t[p].ls,t[q].ls,l,mid,k-rsum);
}
} T;
int main() {
int n=read(),K=read(),L=read(),R=read();
for (re int i=1;i<=n;++i) a[i]=read();
for (re int i=1;i<=n;++i) s[i]=s[i-1]+a[i];
for (re int i=1;i<=n;++i) S[i]=s[i];
sort(S+1,S+n+1); int top=unique(S+1,S+n+1)-S-1;
for (re int i=1;i<=n;++i) s[i]=lower_bound(S+1,S+top+1,s[i])-S;
for (re int i=1;i<=n;++i) T.modify(rt[i],rt[i-1],1,top,s[i],1);
for (re int i=1;i+L-1<=n;++i) {
int j=i+L-1,k=min(i+R-1,n);
int v=S[T.query(rt[j-1],rt[k],1,top,1)]-S[s[i-1]];
Q.push((node){i,1,v});
}
ll ans=0;
while (K--) {
node tp=Q.top(); Q.pop();
ans+=tp.val; ++tp.cnt;
int lim=min(n,tp.p+R-1)-(tp.p+L-1)+1;
if (tp.cnt>lim) continue;
int i=tp.p+L-1,j=min(tp.p+R-1,n);
int v=S[T.query(rt[i-1],rt[j],1,top,tp.cnt)]-S[s[tp.p-1]];
Q.push((node){tp.p,tp.cnt,v});
}
printf("%lld\n",ans);
return 0;
}
细节哪里多了,异或粽子随便写啊(
orz smy 异或粽子大聚聚
Orz fAKe5307!
可是窝写了好久
/kk