【线段树 优先队列】洛谷 P2048 超级钢琴
2021-06-03 18:12:00 # ACM

题链

求其前缀和，对于每一个$i$，可选值的范围是$[i+L-1,i+R-1]$，假设选了$pos$，那么得到的贡献就是$a[pos]-a[i-1]$，也就是说需要选择前$m$大的值相加；

如果对于一个$i$，我在它可选值范围内选了$pos$，得到贡献后，对于$i$的下一个最大值可能在$[i-L+1,pos-1]$内，或者$[pos+1,i+R-1]$内；

用优先队列维护元组{$i$,$i$的可选值范围,该范围内最大值的位置$pos$}，按$a[pos] - a[i-1]$的值从大到小；

考虑用线段树维护区间最大值和最大值所在位置；

一开始就将每一个$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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <bits/stdc++.h>
using namespace std;
#define ls rt<<1
#define rs rt<<1|1
#define LL long long
#define PI acos(-1.0)
#define eps 1e-8
#define Pair pair<double,double>
// notice
#define mod 998244353 
#define MAXN 2e6
#define MS 500009

LL n,m;
LL cl,cr;
LL a[MS];
struct node{
	LL pos,val;
}p[MS<<2];
struct nod{
	LL o,l,r,pos,val;
};
priority_queue<nod > Q;

bool operator < (nod t1,nod t2){
	return t1.val-a[t1.o-1] < t2.val-a[t2.o-1];
}

void push_up(int rt){
	p[rt].val = max(p[ls].val,p[rs].val);
	if(p[ls].val >= p[rs].val)
		p[rt].pos = p[ls].pos;
	else
		p[rt].pos = p[rs].pos;
}

void build(int l,int r,int rt){
	if(l == r){
		p[rt] = {l,a[l]};
		return;
	}
	int m = l+r>>1;
	build(l,m,ls);
	build(m+1,r,rs);
	push_up(rt);
}

node query(int L,int R,int l,int r,int rt){
	if(L <= l && r <= R){
		return p[rt];
	}
	int m = l+r>>1;
	if(m < L) return query(L,R,m+1,r,rs);
	else if(m >= R) return query(L,R,l,m,ls);
	else{
		node ans;
		node t1 = query(L,R,l,m,ls);
		node t2 = query(L,R,m+1,r,rs);
		ans.val = max(t1.val,t2.val);
		if(t1.val >= t2.val) 
			ans.pos = t1.pos;
		else 
			ans.pos = t2.pos;
		return ans;
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m >> cl >> cr;
	for(int i=1;i<=n;i++){
		cin >> a[i];
		a[i] += a[i-1];
	}
	build(1,n,1);
	for(int i=1;i+cl-1<=n;i++){
		LL tl = i+cl-1;
		LL tr = min(i+cr-1,n);
		node t = query(tl,tr,1,n,1);
		Q.push({i,tl,tr,t.pos,t.val});
	}
	LL ans = 0;
	while(m--){
		nod cc = Q.top();
		Q.pop();
		ans += cc.val - a[cc.o-1];
		if(cc.l <= cc.pos-1){
			node ql = query(cc.l,cc.pos-1,1,n,1);
			Q.push({cc.o,cc.l,cc.pos-1,ql.pos,ql.val});
		}
		if(cc.pos+1 <= cc.r){
			node qr = query(cc.pos+1,cc.r,1,n,1);
			Q.push({cc.o,cc.pos+1,cc.r,qr.pos,qr.val});
		}
	}
	cout << ans << "\n";

	return 0;
}

Prev
2021-06-03 18:12:00 # ACM
Next