ABC281E 题解

\(\mathcal Solution\)

本题的思路类似于对顶堆。

用两个 multiset 来维护。

\(S_1\) 为第一个 multiset；

\(S_2\) 为第二个 multiset。

\(S_1\) 维护前 \(K\) 个值，\(S_2\) 维护预选的值。

当进入一个数 \(x\)，则将 \(x \in S_2\)。

1. 如果 \(\mathrm{length}(S_1) < K\)，则将 \(S_2\) 的最小值加入 \(S_1\)。

2. 判断 \(S_2\) 的最小值，即 \(S_2\) 的开头，与 \(S_1\) 的最大值，即 \(S_1\) 的结尾，判断大小关系，如果小于，则替换。

3. 输出 \(\mathrm{ans}_i\)。

4. 在运行完以上操作后，如果 \(i \ge m\) 时，将 \(A_{i - M + 1}\) 删除，即判断 \(A_{i - M + 1}\) 所在的集合将他删除。

5. 重复 \(\mathit{1} \sim \mathit{4}\) 操作。

\(\mathcal Code\)

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <cmath>
#include <sstream>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>

#define x first
#define y second
#define IOS ios::sync_with_stdio(false)
#define cit cin.tie(0)
#define cot cout.tie(0)

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;

const int N = 200010, M = 100010, MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const LL LLINF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-8;

int n, m, k;
int w[N];

void solve()
{
	cin >> n >> m >> k;
	
	multiset<int> S;
	multiset<int> S2;
	for (int i = 1; i <= n; i ++ ) cin >> w[i];
	
	LL res = 0;
	for (int i = 1; i <= n; i ++ )
	{
		S2.insert(w[i]);
		while (S.size() < k && S2.size()) res += *S2.begin(), S.insert(*S2.begin()), S2.erase(S2.begin());
		while (S2.size() && (*S2.begin()) < (*S.rbegin())) // 维护序列
		{
			res -= *S.rbegin();
			res += *S2.begin();
			S2.insert(*S.rbegin());
			S.erase(S.find(*S.rbegin()));
			S.insert(*S2.begin());
			S2.erase(S2.begin());
		}
		if (i >= m)
		{
			cout << res << ' ';
			int x = w[i - m + 1];
			if (S.find(x) != S.end()) res -= x, S.erase(S.find(x)); // 只有在 S 集合中才需要减。
			else S2.erase(S2.find(x));
		}
	}
}

int main()
{
	IOS;
	cit, cot;
	int T = 1;
//	cin >> T;
	while (T -- ) solve();
	return 0;
}