牛客 D 无限的韵律源点 （对顶堆+滑动窗口）

题目链接

思路

本题的重点在于 recent best部分，即指定下标和指定长度的区间 k 最大值，这实际上是区间 k 最值的***版。因此可以选择主席树，划分树等数据结构直接维护。由于本题固定长度的限制，实际上可以借助对顶堆，通过滑动窗口的思想直接维护。开一个小根堆，维护前rb大的值，盛下的维护后ra-rb小的值
可以直接用set替代堆，实现两个部分的维护

代码

#include<iostream>
#include<set>
#include<algorithm>
#include<vector>

using namespace std;
using ll = long long;
using pii = pair<int, int>;

#define x first
#define y second

int main() {
	int n, b, ra, rb;
	cin >> n >> b >> ra >> rb;
	vector<int> nums(n);
	for (int i = 0; i < n; i++) cin >> nums[i];
	multiset<pii> s, sx;
	multiset<pii, greater<pii>> sy;

	ll sum1 = 0, sum2 = 0;


	ll ans = 0;
	for (int i = 0; i < n; i++) {
		s.insert({ nums[i],i });
		sum1 += nums[i];
		while (s.size() > b) {
			sum1 -= s.begin()->x;
			s.erase(s.begin());
		}
		if (i >= ra) {
			int j = i - ra;
			if (sx.count({ nums[j],j })) sx.erase({ nums[j],j }), sum2 -= nums[j];
			else if (sy.count({ nums[j],j })) sy.erase({ nums[j],j });
		}
		if (sx.size() && nums[i] >= sx.begin()->first) sx.insert({ nums[i],i }), sum2 += nums[i];
		else sy.insert({ nums[i],i });
		
		while (sx.size() < rb && sy.size()) {
			sx.insert(*sy.begin());
			sum2 += sy.begin()->x;
			sy.erase(sy.begin());
		}
		while(sx.size()>rb){
			sum2 -= sx.begin()->x;
			sy.insert(*sx.begin());
			sx.erase(sx.begin());
		}
		ans = max(ans, sum1 + sum2);
	}
	cout << ans << endl;
	return 0;
}

思路2

发现了一种牛批的线段树做法，下面贴上大佬代码（这种做法只适用于固定长度（或每次长度常数级别的变化））

#include<iostream>
#include<set>
#include<algorithm>
using namespace std;
typedef long long ll;

#define N 200000

int i, j, k, n, m, t, a[N + 50], mp[N + 50], it;
set<pair<int, int> > s1, s2;
ll res, tot;

struct SB {
#define md ((l+r)/2)
#define ls (id*2)
#define rs (ls+1)
	ll f[N * 4 + 50], g[N * 4 + 50];//f元素的个数，g区间和
	void add(int id, int l, int r, int x, int y) {
		if (l == r) {
			f[id] += y; g[id] += mp[l] * y; return;
		}
		if (x <= md)add(ls, l, md, x, y);
		else add(rs, md + 1, r, x, y);
		f[id] = f[ls] + f[rs]; g[id] = g[ls] + g[rs];
		//cout<<"nmsl "<<l<<' '<<r<<' '<<f[id]<<' '<<g[id]<<endl;
	}
	ll get(int id, int l, int r, int w) {
		//cout<<"NMSL "<<id<<' '<<l<<' '<<r<<' '<<w<<' '<<f[id]<<' '<<g[id]<<endl;
		if (f[id] < w)exit(1);
		if (l == r) {
			return 1ll * mp[l] * w;
		}
		if (f[id] == w) {
			return g[id];
		}
		if (f[rs] >= w) {
			return get(rs, md + 1, r, w);
		}
		return g[rs] + get(ls, l, md, w - f[rs]);
	}
}sb, sb2;

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int ra, rb;
	cin >> n >> m >> ra >> rb;
	for (i = 1; i <= n; i++) {
		cin >> a[i]; mp[++it] = a[i];
	}
	sort(mp + 1, mp + it + 1); it = unique(mp + 1, mp + it + 1) - mp - 1;
	for (i = 1; i <= n; i++) {
		a[i] = lower_bound(mp + 1, mp + it + 1, a[i]) - mp;
		//cout<<"nmsl "<<i<<' '<<a[i]<<endl;
	}
	for (i = 1; i <= n; i++) {
		//cout<<"NMSL "<<i<<' '<<it<<endl;
		sb.add(1, 1, it, a[i], 1);
		sb2.add(1, 1, it, a[i], 1);
		if (i > ra) {
			sb2.add(1, 1, it, a[i - ra], -1);
		}
		//cout<<"nmsl"<<endl;
		tot = sb.get(1, 1, it, min(i, m)) + sb2.get(1, 1, it, min(i, rb));
		res = max(res, tot);
	}
	cout << res;
}