「NOI2010」超级钢琴 - 堆+线段树

题目大意

给一段区间，求出区间内的前k大连续和之和（每一段连续和长度满足>=l、<=r）

---

初步思想

对于k大k小总结本$P2^5+1$有一系列处理方法，其中我们考虑可行的有：

---

• 数据结构
  平衡树肯定不好做，维护子树最大连续和似乎有误，而且长度没法满足要求。
  那么可以考虑主席树，主席树擅长区间k大k小，可以用主席树来处理本题，但常数巨大，本处不做讨论。
• 堆
  堆维护k大k小的两个思路中，（$P2^5+1$）
  第二个思路更好维护，故得出初步思想。

---

维护方法

我们可以固定一个端点，那么另一个端点所在范围即可确定。
如下图：

因此我们可以做一个前缀和，在i点固定的情况下，找到范围内的最小值即可得到当前最大连续和。
当当前的最大连续和被选定，删除本区间，并加入决策点的左右两个区间。

当已经剔除了k个就退出输出答案。
可以使用RMQ或者线段树维护区间最值，注意具体实现的时候是减去决策点前的前缀和，故区间是[i-R,i-L]。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
	LL num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}
const int maxn=500005;
struct Tree {
	int left,right,min;
	Tree() {}
	Tree(int l,int r,int m):left(l),right(r),min(m) {}
};
int n,k,L,R;
LL sum[maxn],ans=0;
struct Segment_Tree {
	Tree tree[maxn*4];
	#define ls index<<1
	#define rs index<<1|1
	void push_up(int index) {
		if(sum[tree[ls].min]<sum[tree[rs].min])tree[index].min=tree[ls].min;
		else tree[index].min=tree[rs].min;
	} 
	void build(int index,int Left,int Right) {
		tree[index]=Tree(Left,Right,n+1);
		if(Left==Right) {
			tree[index].min=Left;
			return;
		}
		int mid=(Left+Right)>>1;
		build(ls,Left,mid);
		build(rs,mid+1,Right);
		push_up(index);
	}
	int query(int index,int Left,int Right) {
		if(Right<tree[index].left||Left>tree[index].right)return n+1;
		if(Left<=tree[index].left&&Right>=tree[index].right)return tree[index].min;
		int l=query(ls,Left,Right),r=query(rs,Left,Right);
		if(sum[l]<sum[r])return l;
		else return r;
	}
} st;
struct QueNode {
	int i,l,r,p; //i当前点 区间[l,r]最值点p 
	QueNode(int _i,int _l,int _r,int _p):i(_i),l(_l),r(_r),p(_p) {}
	bool operator < (const QueNode& b) const {
		return sum[i]-sum[p]<sum[b.i]-sum[b.p];
	}
};
int main() {
	n=Get_Int();
	k=Get_Int();
	L=Get_Int();
	R=Get_Int();
	for(int i=1; i<=n; i++)sum[i]=sum[i-1]+Get_Int();
	sum[n+1]=0x7fffffff/2;
	st.build(1,0,n);
	priority_queue<QueNode>Q;
	for(int i=1; i<=n; i++)
		if(i-L>=0) {
			int Left=max(i-R,0),Right=i-L;
			Q.push(QueNode(i,Left,Right,st.query(1,Left,Right)));
		}
	for(int i=1; i<=k; i++) {
		QueNode Now=Q.top();
		Q.pop();
		ans+=sum[Now.i]-sum[Now.p];
		if(Now.p-1>=Now.l)Q.push(QueNode(Now.i,Now.l,Now.p-1,st.query(1,Now.l,Now.p-1)));
		if(Now.p+1<=Now.r)Q.push(QueNode(Now.i,Now.p+1,Now.r,st.query(1,Now.p+1,Now.r)));
	}
	printf("%lld\n",ans);
	return 0;
}