洛谷 P6294

首先有一个显而易见的性质：每次取都是取最大的一个数。

然后就变成了加数，取最大值，加数，取最大值。。。

直接单走一个优先队列（

但是很明显这个数据不打算把优先队列放过去。

发现一个数加入集合时，如果它比集合中所有数都大，那它就会马上被拿走。

所以我们单独处理这些数。

把这些数去掉以后，剩下的数被取走的顺序显然是固定的。

考虑到这题值域与 \(n\) 同阶，我们考虑维护一个 \(mx\) 指针代表当前集合中最大的数。

然后每次如果要加进来的数大于 \(mx\)，就可以直接处理。

否则则将这个数所对应的计数器加一。每次暴力减 \(mx\)，直到有一个可以取的数。

单次询问 \(\mathcal O(n)\)。

Code：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100005;
int n, m, p;
int a[N], cnt[N];

void solve(int p) {
	for (int i = 1; i < p; ++i) ++cnt[a[i]];
	int mx = n;
	ll ans = 0;
	for (int i = 1; i <= n; ++i) {
		if (i + p - 1 <= n) {
			if (a[i + p - 1] > mx) {
				if (i & 1) ans += a[i + p - 1];
				else ans -= a[i + p - 1];
				continue;
			}
			++cnt[a[i + p - 1]];
		}
		while (!cnt[mx]) --mx;
		if (i & 1) ans += mx;
		else ans -= mx;
		--cnt[mx];
	}
	printf("%lld\n", ans);
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
	while (m--) scanf("%d", &p), solve(p);
	return 0;
}