「NOI2010」超级钢琴 - 堆+线段树 | Bill Yang's Blog
0%

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

题目大意

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


初步思想

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


  • 数据结构
    平衡树肯定不好做,维护子树最大连续和似乎有误,而且长度没法满足要求。
    那么可以考虑主席树,主席树擅长区间k大k小,可以用主席树来处理本题,但常数巨大,本处不做讨论。

  • 堆维护k大k小的两个思路中,($P2^5+1$)
    第二个思路更好维护,故得出初步思想。

维护方法

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

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

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


代码

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#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;
}
姥爷们赏瓶冰阔落吧~