P8539 「Wdoi-2」來自地上的支援 題解

• 2022 年 9 月 13 日
• 筆記
• 題解

思路

根據題意，如果每次詢問選中的為第 \(x\) 個數，那麼前 \(x-1\) 次操作一定不會選中第 \(x\) 個數。（感覺在說廢話。）

同樣，因為第 \(x\) 個數必須被選中 \(k\) 次，根據題意，不難發現這 \(k\) 次選中一定是從第 \(x\) 次操作到 \(x+k-1\) 次操作被選中。因為如果某個數在某次操作時沒有被選中，那麼他在後面的操作中肯定不會再次被選中。

根據上面的思路，我們要修改的最小值 \(s\) 必須大於等於前 \(x-1\) 個數進行 \(x-1\) 次操作後的最大值，我們可以用一個前綴數組來維護，數組的每個值 \(pre_i\) 表示前 \(i-1\) 個數進行 \(i-1\) 次操作後的最大值，然後再向後枚舉 \(k-1\) 個數，每次都和進行過若干次操作後的最大值比較，如果枚舉到的值比最大值大，就講當前的最大值修改為枚舉到的值加一（操作的第二個性質），這樣就可以得到答案。

這時你就可以得到 \(65\) 分的好成績。

優化

很顯然，對於上面向後枚舉 \(k-1\) 個數的操作是可以進行優化的。

因為要區間查詢最大值，所以不妨考慮一下線段樹，但現在問題出現在如果維護最大值上。

我們可以考慮在維護線段樹時同時記錄下最大值和最大值所在的坐標。然後在兩個數相比較的時候，比較 \(a_i+(j-i)\times v\) 和 \(a_j\) 的大小（\(i\le j\))。根據這樣比較的結果選出最大值來，這樣我們只需要把 \(s\) 修改為 \(\max\left\{ pre_x,a_p-(p-x)\times v+1 \right\}\) （\(p\) 表示最大值所在的下標）即可。

程式碼

#include <bits/stdc++.h>
#define int long long
#define ls x<<1
#define rs x<<1|1
#define N 2000010
using namespace std;

struct node {
	int val, st;
};
int n, m, v, a[N], pre[N], ans1, ans2;
node maxn[N << 2];

node max(node x, node y) {
	if (x.st > y.st) {
		if ((x.st - y.st)*v + y.val < x.val) {
			return x;
		} else {
			return y;
		}
	} else {
		if ((y.st - x.st)*v + x.val < y.val) {
			return y;
		} else {
			return x;
		}
	}

}

void bulid(int x, int l, int r) {
	if (l == r) {
		maxn[x] = node{a[l], l};
		return;
	}

	int mid = l + r >> 1;
	bulid(ls, l, mid);
	bulid(rs, mid + 1, r);
	maxn[x] = max(maxn[ls], maxn[rs]);
}

node query(int x, int l, int r, int L, int R) {
	if (l >= L && r <= R) {
		return maxn[x];
	}


	int mid = l + r >> 1;

	if (R <= mid) {
		return query(ls, l, mid, L, R);
	} else if (L > mid) {
		return query(rs, mid + 1, r, L, R);
	} else {
		return max(query(ls, l, mid, L, R), query(rs, mid + 1, r, L, R));
	}
}

signed main() {
	scanf("%lld%lld%lld", &n, &m, &v);
	int maxn = 0;

	for (int i = 1; i <= n; i++) {

		scanf("%lld", &a[i]);
		pre[i] = maxn;
		maxn = max(maxn, a[i]) + v;
	}

	bulid(1, 1, n);

	while (m--) {
		int x, k;
		scanf("%lld%lld", &x, &k);

		if (k > n - x + 1) {
			continue;
		}

		int s = pre[x];
		if(k==1){
			ans1 ^= s;
			ans2 += s;
			continue;
		}
		node tmp = query(1, 1, n, x + 1, x + k - 1);

		if (s <= tmp.val - (tmp.st - x)*v) {
			s = tmp.val - (tmp.st - x) * v + 1;
		}

		ans1 ^= s;
		ans2 += s;
	}

	printf("%lld %lld", ans1, ans2);
	return 0;
}