牛客 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;
}