我竟然又在写主席树
现在可是九月啦，我却还在写这种noip不可能考的算法
我觉得我真的要凉
题意很明确，就是给你一个序列，让从中选择\(k\)段连续的序列，长度必须大于等于\(L\)小于等于\(R\)，让这\(k\)段的和最大
本来认为这是一个非常精妙的\(RMQ\)问题，但是经过一番思考之后发现不会
智商不够，数据结构来凑
看到一个区间的和，我们很自然的想到前缀和，之后我们先枚举每一个数\(x\)作为区间的结尾，之后从\([x-R,x-L]\)中选出最小值来，这样就得到了以每个数作为结尾的符合长度限制的区间最大值，之后我们用一个堆来维护
之后每次取出堆顶位置，统计答案，显然这个我们只考虑了这个位置作为结尾的最大值，没有考虑剩下的可能也会被计入答案的值，所以我们用主席树来找到下一个次小的前缀和，再放到堆里维护
代码
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
#define re register
#define maxn 500005
#define max(a,b) ((a)>(b)?(a):(b))
#define mp std::make_pair
typedef std::pair<int,int> pii;
std::priority_queue<pii,std::vector<pii>,std::less<pii> > q;
int pre[maxn],a[maxn],b[maxn],to[maxn],rt[maxn],num[maxn],M[maxn];
int L,R,K,n,tot,cnt;
int ls[maxn*25],rs[maxn*25],d[maxn*25];
int build(int x,int y)
{
int root=++cnt;
if(x==y) return root;
int mid=x+y>>1;
ls[root]=build(x,mid);
rs[root]=build(mid+1,y);
return root;
}
int change(int pre,int x,int y,int pos)
{
int root=++cnt;
d[root]=d[pre]+1;
if(x==y) return root;
ls[root]=ls[pre],rs[root]=rs[pre];
int mid=x+y>>1;
if(pos<=mid) ls[root]=change(ls[pre],x,mid,pos);
else rs[root]=change(rs[pre],mid+1,y,pos);
return root;
}
int query(int p1,int p2,int x,int y,int k)
{
if(x==y) return b[x];
int now=d[ls[p1]]-d[ls[p2]];
int mid=x+y>>1;
if(k>now) return query(rs[p1],rs[p2],mid+1,y,k-now);
return query(ls[p1],ls[p2],x,mid,k);
}
inline int read()
{
char c=getchar();
int x=0,r=1;
while(c<'0'||c>'9')
{
if(c=='-') r=-1;
c=getchar();
}
while(c>='0'&&c<='9')
x=(x<<3)+(x<<1)+c-48,c=getchar();
return x*r;
}
inline int Find(int x)
{
int l=1,r=tot;
while(l<=r)
{
int mid=l+r>>1;
if(b[mid]==x) return mid;
else
{
if(b[mid]>x) r=mid-1;
else l=mid+1;
}
}
}
inline int _to(int x)
{
if(x<0) return 500002;
return x;
}
int main()
{
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++)
pre[i]=pre[i-1]+a[i],b[i]=pre[i];
b[n+1]=0;
std::sort(b+1,b+n+2);
tot=std::unique(b+1,b+2+n)-b-1;
for(re int i=0;i<=n;i++)
to[i]=Find(pre[i]);
rt[500002]=build(1,tot);
rt[0]=change(rt[500002],1,tot,to[0]);
for(re int i=1;i<=n;i++)
rt[i]=change(rt[i-1],1,tot,to[i]);
int t;
for(re int i=L;i<=n;i++)
t=pre[i]-query(rt[i-L],rt[_to(i-R-1)],1,tot,num[i]+1),num[i]++,q.push(mp(t,i));
M[L]=1;
for(re int i=L+1;i<=R;i++)
M[i]=M[i-1]+1;
for(re int i=R+1;i<=n;i++)
M[i]=R-L+1;
long long ans=0;
while(K--)
{
int k=q.top().second;
ans+=q.top().first;
q.pop();
if(num[k]<M[k]) num[k]++,q.push(mp(pre[k]-query(rt[k-L],rt[_to(k-R-1)],1,tot,num[k]),k));
}
std::cout<<ans;
return 0;
}
时间复杂度\(O(nlogn+klogn)\)，好像还要比\(ST\)表快一些