自动搬运

查看原文

来自洛谷，原作者为

	super蒟蒻 ( ᗜ ˰ ᗜ )​

搬运于2025-08-24 22:06:46，当前版本为作者最后更新于2021-12-06 15:19:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

提供一个线段树的做法。

首先 $a_{x-1}-1,a_x-1,a_{x+1}-1$ 不会改变三者的大小关系， $a_x$ 依然是这三个数中最大的，因此左右两边必不会选到，要让 $a_x=0$ 只能对着 $x$ 操作 $a_x$ 次（然后它左右两边顺理成章的也变成了零）。

所以原题实际上是要维护一个被减的数的集合，这些数在原序列互不相邻且符合操作的要求，然后输出这些数的和。

考虑用线段树维护这个集合的和。

首先叶子的答案是本身，然后我们考虑合并两个区间。

发现如果 左区间的右端点没有被选 或者 右区间的左端点没有被选，这两个区间是互不影响的，答案直接相加即可。

但是像下面的两个区间：（ X 表示被选进集合中）

[1 3 4] + [5 5 4] -> [X . X] + [X . X] -> [. X . X . X]

因为 X 互不相邻，合并的时候要强制一个区间的端点不选（即当它不存在）。

因此我们要计算四个值。

$s(l,r,0/1/2/3)$ 表示按照题目要求将 $[l,r]$ 这个区间清零要多少次操作，第三维的 $1$ 表示这个区间的左端点不用管， $2$ 表示右端点不用管 ， $3$ 表示两个端点都不用管， $0$ 表示都要管。

同时为了辅助合并，还要记 $lm(l,r,0/1/2/3)$ 表示 $[l,r]$ 这个区间在 $0/1/2/3$ 这四种情况下左端点有没有被选， $rm(l,r,0/1/2/3)$ 右端点同理。

分类讨论维护即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int read() {
	char ch = getchar();
	int x = 0, pd = 0;
	while (ch < '0' || ch > '9') pd |= ch == '-', ch = getchar();
	while ('0' <= ch && ch <= '9') x = x * 10 + (ch ^ 48), ch = getchar();
	return pd ? -x : x;
}
const int maxn = 100005;
int n, m, a[maxn];
#define ls (o << 1)
#define rs (o << 1 | 1)
#define lson ls,l,mid
#define rson rs,mid+1,r
bool lm[maxn << 2][4], rm[maxn << 2][4];
ll s[maxn << 2][4];
void pushup(int o, int l, int r) {
	int mid = (l + r) >> 1;
	if (rm[ls][0] && lm[rs][0]) {
		if (a[mid] >= a[mid + 1]) {
			lm[o][0] = lm[ls][0], rm[o][0] = rm[rs][1];
			s[o][0] = s[ls][0] + s[rs][1];
		} else{
			lm[o][0] = lm[ls][2], rm[o][0] = rm[rs][0];
			s[o][0] = s[ls][2] + s[rs][0];
		}
	} else lm[o][0] = lm[ls][0], rm[o][0] = rm[rs][0], s[o][0] = s[ls][0] + s[rs][0];

	if (rm[ls][1] && lm[rs][0]) {
		if (a[mid] >= a[mid + 1]) {
			rm[o][1] = rm[rs][1];
			s[o][1] = s[ls][1] + s[rs][1];
		} else {
			rm[o][1] = rm[rs][0];
			s[o][1] = s[ls][3] + s[rs][0];
		}
	} else rm[o][1] = rm[rs][0], s[o][1] = s[ls][1] + s[rs][0];

	if (rm[ls][0] && lm[rs][2]) {
		if (a[mid] >= a[mid + 1]) {
			lm[o][2] = lm[ls][0];
			s[o][2] = s[ls][0] + s[rs][3];
		} else {
			lm[o][2] = lm[ls][2];
			s[o][2] = s[ls][2] + s[rs][2];
		}
	} else lm[o][2] = lm[ls][0], s[o][2] = s[ls][0] + s[rs][2];

	if (rm[ls][1] && lm[rs][2]) {
		if (a[mid] >= a[mid + 1]) s[o][3] = s[ls][1] + s[rs][3];
		else s[o][3] = s[ls][3] + s[rs][2];
	} else s[o][3] = s[ls][1] + s[rs][2];
}
void build(int o, int l, int r) {
	if (l == r) {
		s[o][0] = a[l] = read();
		lm[o][0] = rm[o][0] = 1;
		return;
	}
	int mid = (l + r) >> 1;
	build(lson), build(rson), pushup(o, l, r);
}
void upd(int o, int l, int r, int x) {
	if (l == r) { s[o][0] = a[l]; return; }
	int mid = (l + r) >> 1;
	if (x <= mid) upd(lson, x);
	else upd(rson, x);
	pushup(o, l, r);
}
int main() {
	n = read();
	build(1, 1, n);
	m = read();
	while (m--) {
		int x = read(), y = read();
		a[x] = y, upd(1, 1, n, x);
		printf("%lld\n", s[1][0]);
	}
	return 0;
}