[NOI2010] 超级钢琴 题解

说点闲话

原本不想写这个题解的

但是看到我的代码居然长度为2048B->刚好2KiB，然后还跟题号相同QAQ

题目翻译

给你一段序列，求出其中从第\(1\)大到第\(k\)大的子区间的和。

思路解析

首先可以想到一个简单的暴力，对于每一个区间开头\(i\)，和区间结尾\(j\)，都求出其值，然后排序，将前\(k\)大的值加起来即可。

但是这个暴力时间复杂度太大了，是\(O(n^2log_n)\)，显然我们是不能接受的，但是分析数据范围之后,我们就知道在\(O(nlog_n)\)的时间以内应该就是正解。那么回想我们的暴力，我们是将区间开头和区间结尾各自都枚举了一遍，但是如果我们只枚举一个呢。所以我们想到优化，先记录区间的前缀和，方便求出各个区间的和，就是枚举以各个\(StLeft\)为开头的区间，求出\(StLeft+L-1\)到\(StLeft+R-1\)中前缀和最大的一个（St表/线段树维护），减去\(StLeft-1\)的前缀和，即可得到以\(StLeft\)开头，合法的区间中，区间和最大的一个（注意处理数组越界问题）。

然后将所有的五元组塞入一个堆里面，从堆中取\(k\)次值，每次取出之后将答案累计进去。但是如果只是单纯地这么做正确性是不能保证的，因为很容易想到可能有两个\(StLeft\)为同一个值，而\(MaxPos\)不同的五元组都需要被计入答案。所以我们还要做的是将取出来的五元组分裂，然后再塞回堆里面。只需要将五元组的\(Left，Right\)按\(MaxPos\)分裂为两部分，之后再对新的两个五元组求出\(MaxPos\)塞回堆里面即可。具体而言，将原本的\(Left，Right\)分裂为\(Left，MaxPos-1\)和\(MaxPos+1，Right\)（记得特判，防止越界）。

关于Debug

我做这道题的时候挺顺的，交的时候一遍就过了。

可能比较需要注意的是：

1）初始塞五元组的时候，防止\(Left，Right\)越界

2）分裂的时候不要让新的五元组的\(Left>Right\)了

3）线段树不要写错了（我就是写错了线段树没过样例QAQ）

关于代码

#include <cstdio>
#include <cstring>
#include <queue>
#define MAXN 500010
using namespace std;
int OLine[MAXN],Sum[MAXN],Total=0,RetP=0,RetV=0,n,k,l,r;
long long Ans=0;
struct O{
	int Value,StLeft,Left,Right,Position;
};
bool operator<(O a,O b){
	return a.Value<b.Value;
}
priority_queue <O> Q;
struct N{
	int Left,Right;
	int Value,Pos;
	int LeftN,RightN;
}Node[MAXN<<2];
void Build(int Left,int Right){
	Total++;
	Node[Total].Left=Left;
	Node[Total].Right=Right;
	if(Left==Right){Node[Total].Value=Sum[Left]; Node[Total].Pos=Left; return;}
	int Now=Total,Mid=(Left+Right)>>1;
	Node[Now].LeftN=Total+1;Build(Left,Mid);
	Node[Now].RightN=Total+1;Build(Mid+1,Right);
	Node[Now].Value=Node[Node[Now].LeftN].Value,Node[Now].Pos=Node[Node[Now].LeftN].Pos;
	if(Node[Node[Now].RightN].Value>Node[Now].Value){
		Node[Now].Value=Node[Node[Now].RightN].Value,Node[Now].Pos=Node[Node[Now].RightN].Pos;
	}
}
void Query(int Now,int Left,int Right){
	if(Node[Now].Left>=Left&&Node[Now].Right<=Right){if(Node[Now].Value>RetV){RetV=Node[Now].Value;RetP=Node[Now].Pos;}return;}
	else if(Node[Now].Left>Right||Node[Now].Right<Left){return;}
	else{
		Query(Node[Now].LeftN,Left,Right);
		Query(Node[Now].RightN,Left,Right); 
	}
}
O Make(int StL,int Left,int Right){
	O Ret;
	Ret.StLeft=StL;
	Ret.Left=Left;
	Ret.Right=Right;
	RetP=-1<<30,RetV=-1<<30;
	Query(1,Left,Right);
	Ret.Position=RetP;
	Ret.Value=RetV;
	Ret.Value-=Sum[StL-1];
	return Ret;
}
int main(){
	scanf("%d%d%d%d",&n,&k,&l,&r);
	Sum[0]=0;
	for(int i=1;i<=n;i++){
		scanf("%d",&OLine[i]);
		Sum[i]=Sum[i-1]+OLine[i];
	}
	Build(1,n);
	for(int i=1;i<=n;i++){
		int LL,RR;
		if(i+l-1<=n) LL=i+l-1;
		else{break;}
		if(i+r-1<=n) RR=i+r-1;
		else RR=n;
		Q.push(Make(i,LL,RR));
	}
	while(k--){
		Ans+=Q.top().Value;
		int P=Q.top().Position;
		int LL=Q.top().Left,RR=Q.top().Right,STLL=Q.top().StLeft;
		Q.pop();
		if(P!=LL) Q.push(Make(STLL,LL,P-1));
		if(P!=RR) Q.push(Make(STLL,P+1,RR));
	}
	printf("%lld",Ans);
	return 0;
}