传送门
题意：有一个长为n的数列A,定义区间[l, r]的权值为\(\sum_{i=l}^{r}a_i\).选出k个不相同的区间,使得它们的权值和最大.并满足每个选出的区间长度∈[L, R].
分析：最最最基本的,既然是要求区间和,就要想到前缀和.然后暴力做法是\(n^2\)枚举所有区间,把符合条件(区间长度的限制)的区间的区间和保存起来,然后排个序,输出前k个的和.
考虑这样一个问题,如果你已经知道了区间的右端点i,题目又限制了合法区间的长度∈[L,R],所以这个以i为右端点的区间的区间和就是\(sum[i]-sum[j-1]\)的值,其中i-j+1∈[L,R],即j∈[i+1-R,i+1-L].要使\(sum[i]-sum[j-1]\)的值最大,因为sum[i]的值是固定的了,所以sum[j-1]要最小.即我们要在区间[i+1-R,i+1-L]中找到一个j,使得sum[j-1]最小.
如果我们对于每一个右端点i都for循环[i+1-R,i+1-L],找到对应的左端点j,最坏情况下,时间复杂度还是\(n^2\).我们现在正在求解的问题是什么?在区间[i+1-R,i+1-L]找最小值,这不是RMQ问题么,那不就可以用ST求解么?然后本题中,我们为了方便,将RMQ(求区间最值)用于求区间最小值的下标,具体见代码实现.
接下来贪心地想我们每次都选最优的子段，这样选k次显然就是我们所要的结果，那怎么每次都找到最优解呢？可以用堆来将所有解存进去，每次堆顶的元素就是最优解.
综上,我们可以枚举区间右端点L-n,结构体建立一个四元组(right,l,r,pos)分别表示区间右端点,左端点的左边界,左端点的右边界,左端点的下标(RMQ就用于求左端点的下标).看到这里,我们会有疑问既然都知道了左端点的下标pos,为什么还要记录左端点的左右边界[l,r],这是因为对于一个右端点right,它可能对答案产生多次贡献,所以我们取完pos后,把pos从区间[l,r]中删掉,然后把(right,l,pos-1,pos')和(right,pos+1,r,pos'')丢进堆里(丢的时候判断一下pos是否正好就是l或者r).
关于前缀和数组sum[ ]和最后的答案ans,记得开long long.
P.S.好像思路不是特别地清晰,这道题对我来说太难了...
int n,k,L,R,RMQ[500005][25];
long long ans,sum[500005];
struct data{
int right,l,r,pos;
data(int a,int b,int c,int d){right=a;l=b;r=c;pos=d;}
bool operator <(const data &a)const{return sum[right]-sum[pos-1]<sum[a.right]-sum[a.pos-1];}
//重载运算符,建立大根堆
//保证堆顶的四元组是当前的最优解
};
priority_queue<data> q;
int min_pos(int x,int y){
if(sum[x-1]<sum[y-1])return x;
return y;
}
int find(int x,int y){
int k=log2(y-x+1);
return min_pos(RMQ[x][k],RMQ[y-(1<<k)+1][k]);
}
int main(){
n=read();k=read();L=read();R=read();
for(int i=1;i<=n;i++){
sum[i]=sum[i-1]+read();//直接计算前缀和
RMQ[i][0]=i;//初始化
//本来RMQ数组记录的是区间最小值,
//但本题为了方便,直接记录区间最小值的下标
}
for(int j=1;j<=20;j++)//2^20已经绰绰有余了
for(int i=1;i+(1<<j)-1<=n;i++)
RMQ[i][j]=min_pos(RMQ[i][j-1],RMQ[i+(1<<(j-1))][j-1]);
//min_pos函数返回下标
for(int i=L;i<=n;i++){//枚举区间右端点.
int l=max(1,i+1-R),r=i+1-L;
//l,r分别是区间左端点的左右边界
//这里有一个细节,左边界与1取man,因为i+1-R可能<=0
q.push(data(i,l,r,find(l,r)));
//直接把data四元组放入大根堆中
//find函数返回区间[l,r]中最小值的下标
}
while(k--){
data now=q.top();q.pop();
ans+=sum[now.right]-sum[now.pos-1];
//每次直接取堆顶,然后累加ans
if(now.pos>now.l)q.push(data(now.right,now.l,now.pos-1,find(now.l,now.pos-1)));
if(now.pos<now.r)q.push(data(now.right,now.pos+1,now.r,find(now.pos+1,now.r)));
//取完后还要放回去,放回去时判断一下
//本次取的now.pos是否在边界上,不在边界上,才放回去
}
printf("%lld\n",ans);
return 0;
}
