P2048 [NOI2010] 超级钢琴

题目链接

其实这道题在我刚学 oi 两个月 (2023.3) 就见过了

当时是作为 st 表的一个例题出现的， 我学 st 表就已经学得迷迷糊糊的了， 更别说这题了哈哈

所以这是第二次见到他， 必须写了（这一次他是作为 NOIP 模拟赛的一个部分分做法出现的）

思路

不错的限制：每个和弦都是连续的

所以可以考虑一个基于起点位置的贪心

按照常规的思路 \(idx, p, v\) 表示以 \(idx\) 为起点， 向后延伸到了 \(p\) 位置， 当前位置的贡献为 \(v\)

然后把他们丢进优先队列， 每次取堆顶， 把 \(p\) 向后延伸一位即可

但是

这个序列不是单调的， 因为中间有一些负数

这就意味着距离 \(idx\) 为 \(R\) 的点到 \(idx\) 的这段序列并不一定是最大的

所以上述做法只能用于一个削弱版的本题

该如何改进呢

其实并不难， 但是我一开始没想出来

设 \([l, r]\ \ \ idx \ \ \ v\) 表示当前可选的右端点在区间 \([l, r]\) 中， 其中取到最大值的是下标为 \(idx\) 的右端点， 贡献为 \(v\)

这样， 每次取完堆顶后， \([l, r]\) 就分成了 \([l, idx - 1]\) 和 \([idx + 1, r]\) 两个区间， 对这两个区间再分别算出 \(v\) 和 \(idx\) 即可

这一步可以用 st 表实现， 是 \(O(1)\)

总时间复杂度 \(O(k\ log\ n)\)

代码

#include <bits/stdc++.h>
#define int long long
// #pragma GCC optimize(2)
using namespace std;
const int N = 5e5 + 10, Base = 191;

int n, k, l, r;
int a[N];
int st[20][N], ps[20][N];

void Init(){
	for(int i = 1; i < 20; i++){
		for(int j = 0; j + (1 << i) - 1 <= n; j++){
			if(st[i - 1][j] > st[i - 1][j + (1 << (i - 1))]){
				st[i][j] = st[i - 1][j];
				ps[i][j] = ps[i - 1][j];
			}else{
				st[i][j] = st[i - 1][j + (1 << (i - 1))];
				ps[i][j] = ps[i - 1][j + (1 << (i - 1))];
			}
		}
	}
}

struct Ret{
	int maxi, maxid;
};

Ret Query(int l, int r){
	int k = __lg(r - l + 1);

	Ret ret = {0, 0};
	if(st[k][l] > st[k][r - (1 << k) + 1]){
		ret.maxi = st[k][l];
		ret.maxid = ps[k][l];
	}else{
		ret.maxi = st[k][r - (1 << k) + 1];
		ret.maxid = ps[k][r - (1 << k) + 1];		
	}
	return ret;
}

struct Node{
	int idx, l, r, mid, v;

	bool operator < (const Node &p)const{
		return v < p.v;
	}
}tp;
priority_queue <Node> q;

signed main(){
	// freopen("1.in", "r", stdin);

	cin >> n >> k >> l >> r;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		st[0][i] = st[0][i - 1] + a[i];
		ps[0][i] = i;
	}

	Init();
	for(int i = 1; i + l - 1 <= n; i++){
		int ll = i + l - 1, rr = min(i + r - 1, n);
		auto ret = Query(ll, rr);
		q.push({i, ll, rr, ret.maxid, ret.maxi - st[0][i - 1]});
	}

	int sum = 0;
	for(int i = 1; i <= k; i++){
		tp = q.top();
		q.pop();

		sum += tp.v;
		if(tp.mid - 1 >= tp.l){
			int ll = tp.l, rr = tp.mid - 1;
			auto ret = Query(ll, rr);
			q.push({tp.idx, ll, rr, ret.maxid, ret.maxi - st[0][tp.idx - 1]});
		}
		if(tp.mid + 1 <= tp.r){
			int ll = tp.mid + 1, rr = tp.r;
			auto ret = Query(ll, rr);
			q.push({tp.idx, ll, rr, ret.maxid, ret.maxi - st[0][tp.idx - 1]});
		}
	}
	cout << sum << "\n";
}