P8539 「Wdoi-2」来自地上的支援 题解

思路

根据题意，如果每次询问选中的为第 x" role="presentation">x$x$ 个数，那么前 x−1" role="presentation">x−1$x-1$ 次操作一定不会选中第 x" role="presentation">x$x$ 个数。（感觉在说废话。）

同样，因为第 x" role="presentation">x$x$ 个数必须被选中 k" role="presentation">k$k$ 次，根据题意，不难发现这 k" role="presentation">k$k$ 次选中一定是从第 x" role="presentation">x$x$ 次操作到 x+k−1" role="presentation">x+k−1$x+k-1$ 次操作被选中。因为如果某个数在某次操作时没有被选中，那么他在后面的操作中肯定不会再次被选中。

根据上面的思路，我们要修改的最小值 s" role="presentation">s$s$ 必须大于等于前 x−1" role="presentation">x−1$x-1$ 个数进行 x−1" role="presentation">x−1$x-1$ 次操作后的最大值，我们可以用一个前缀数组来维护，数组的每个值 prei" role="presentation">prei$pr{e}_i$ 表示前 i−1" role="presentation">i−1$i-1$ 个数进行 i−1" role="presentation">i−1$i-1$ 次操作后的最大值，然后再向后枚举 k−1" role="presentation">k−1$k-1$ 个数，每次都和进行过若干次操作后的最大值比较，如果枚举到的值比最大值大，就讲当前的最大值修改为枚举到的值加一（操作的第二个性质），这样就可以得到答案。

这时你就可以得到 65" role="presentation">65$65$ 分的好成绩。

优化

很显然，对于上面向后枚举 k−1" role="presentation">k−1$k-1$ 个数的操作是可以进行优化的。

因为要区间查询最大值，所以不妨考虑一下线段树，但现在问题出现在如果维护最大值上。

我们可以考虑在维护线段树时同时记录下最大值和最大值所在的坐标。然后在两个数相比较的时候，比较 ai+(j−i)×v" role="presentation">ai+(j−i)×v$a_i+(j-i)\times v$ 和 aj" role="presentation">aj$a_j$ 的大小（i≤j" role="presentation">i≤j$i\le j$)。根据这样比较的结果选出最大值来，这样我们只需要把 s" role="presentation">s$s$ 修改为 max{prex,ap−(p−x)×v+1}" role="presentation">max{prex,ap−(p−x)×v+1}$max\{pr{e}_x,a_p-(p-x)\times v+1\}$ （p" role="presentation">p$p$ 表示最大值所在的下标）即可。

代码

#include 
#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;
}

• 思路
• 优化
• 代码

__EOF__