Steven_MengのBlog

传送门

强烈谴责出题者,题面都花了好几分钟读。

题意:

给你$\{ A_i\}$,让你从集合$S=\{x|x= \sum _{k=i} ^{j} A[k] , j-i+1 \in[L,R] \}$选出$k$个数,使他们的和尽可能大。

首先考虑一件事,如何表示$[i,j]$。

一种思路是枚举区间长度$l$,$l \in [L,R],[1,l],[2,l+1],[3,l+2] \cdots$,但是这样不好表示。

另一种思路是枚举左端点$i$,$i \in [1,n-L+1] , [i,i+L-1],[i,i+L], \cdots [i,i+R-1]$,这样就有了确定的范围。

我们有一个显然的贪心,要从$S$中选出前$k$大的值。

设$Max(i,j,k)=使\sum _{p=i} ^a A[p]最大的 a,且a \in [j,k]$

考虑$S$中最大值,肯定是$\sum _{j=i} ^{Max(i,i+L-1,i+R-1)} A[j]$中的一个,根据贪心,我们要取走这个最大值,设这个最大值的$i$为$p_1$,设$Max(p_1,p_1+L-1,p_1+R-1)=p_2$那么取走它之后,显然它会分裂成两个,之后的最大值只可能在$Max(p_1,p_1+L-1, p_2-1),Max(p_1,p_2+1,p_1+R-1)$中取到。

于是由上述性质,我们需要用堆维护,每次将某个数取走之后,将分裂成的两个数$push$进去即可。

这个$Max(i,j,k)$也比较好求,$\sum _{p=i} ^a A[p] \Rightarrow sum[a]-sum[i-1]$,用$ST$表维护使$sum[i]$最大的位置即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <bits/stdc++.h>
#define MAXN 500005
#define LOG 25
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^'0');
ch=getchar();
}
return x*f;
}
int a[MAXN],sum[MAXN],n,k,L,R;
namespace RMQ{
int pos[LOG][MAXN],lg[MAXN];
inline int cmp(int x,int y){
return sum[x]<sum[y];
}
inline void Init(){
lg[0]=-1;
for (register int i=1;i<MAXN;++i){
lg[i]=lg[i>>1]+1;
}
for (register int i=1;i<=n;++i) pos[0][i]=i;//注意是位置
for (register int i=1;i<LOG;++i){
for (register int j=1;j+(1<<i)-1<=n;++j){
pos[i][j]=max(pos[i-1][j],pos[i-1][j+(1<<(i-1))],cmp);
}
}
}
inline int Query(int l,int r){
int k=lg[r-l+1];
return max(pos[k][l],pos[k][r-(1<<k)+1],cmp);
}
}
using namespace RMQ;
struct Piano{
int p,l,r,m;
};
inline Piano make(int p,int l,int r){
return Piano{p,l,r,Query(l,r)};
}
inline int Calc(const Piano &A){
return sum[A.m]-sum[A.p-1];
}
inline bool operator < (const Piano &A,const Piano &B){
return Calc(A)<Calc(B);
}
int main(){
n=read(),k=read(),L=read(),R=read();
for (register int i=1;i<=n;++i) a[i]=read();
for (register int i=1;i<=n;++i) sum[i]=sum[i-1]+a[i];
Init();
priority_queue<Piano>Q;
for (register int i=1;i<=n-L+1;++i){
Q.push(make(i,i+L-1,min(i+R-1,n)));
}
long long ans=0;
while (k--){
int p=Q.top().p,l=Q.top().l,r=Q.top().r,m=Q.top().m;
ans+=Calc(Q.top());
Q.pop();
if (l<m) Q.push(make(p,l,m-1));
if (m<r) Q.push(make(p,m+1,r));
//分裂成两个区间
}
printf("%lld\n",ans);
}

 评论