自动搬运

查看原文

来自洛谷，原作者为

	Eray **

搬运于2025-08-24 22:54:23，当前版本为作者最后更新于2024-01-20 10:03:51，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

先来做静态问题，即不带修改。

首先考虑每种长度的棍子都只有偶数根的情况，那么答案就是总棍子数除以 $3$ 下取整。显然答案不会大于这个数，下面构造地证明答案不会小于这个数：

由于所有长度的棍子都是偶数根，所以我们把两根同样长的棍子打包成 一对 棍子。显然不会出现落单的棍子。
如果我们任取 $3$ 对棍子，长度分别为 $a,b,c(a\le b\le c)$，那么可以构造两个三角形：$(a,b,b)$ 和 $(a,c,c)$。容易验证满足题目条件。
重复以上操作，最后棍子只会剩下最多两对。如果最后剩 $0$ 对或 $1$ 对，那么显然不能做出新的三角形了，此时总棍子数为 $6k$ 或 $6k+2$ 的形式（其中 $k$ 为进行上面操作的次数），除以 $3$ 下取整正好是 $2k$，满足我们的结论；如果最后剩 $2$ 对，假设长度为 $a,b(a\le b)$，那么我们可以再构造出一个三角形 $a,b,b$，也满足结论。

现在考虑如果出现奇数根棍子怎么办。我们还是将两根相同的棍子打包成 一对，那么此时会出现若干 落单 的棍子。显然这些落单的棍子只能作为底边和另外一对棍子凑成一个三角形。此时我们的最优策略是贪心地将尽量多的落单棍子做成三角形，然后加上未被做成三角形的那些 对 的答案（即总数除以 $3$ 下取整）。下面证明这一点：

因为一个落单的棍子必须依赖另外一对棍子才能被拼成三角形，所以我们来观察没有落单的棍子。当我们把一个落单的棍子做成三角形时，我们会消耗 $1$ 对棍子。但是如果不将这根落单的棍子做成三角形，我们则会让那些没落单的棍子内部消化，这时则会消耗 $1.5$ 对棍子，即 $3$ 根棍子。所以尽量多将落单的棍子做成三角形一定是更优的。
如果觉得上面那个证明太感性，也可以用数学计算的方法：假设我们将 $x$ 根落单的棍子做成了三角形，并且总共有 $y$ 对棍子，其中 $y\ge x$，那么答案是 $x+\left\lfloor\dfrac{y-2x}{3}\right\rfloor=\left\lfloor\dfrac{x+y}{3}\right\rfloor$，由于 $y$ 不会变，所以显然 $x$ 越大答案越大。

现在的问题就变成了如何让尽量多落单的棍子被做成三角形。这个有一个比较简单的做法。

我们发现如果固定腰的长度，那么底边的长度范围是一段前缀。所以我们可以把腰当成右括号，底边当成左括号，那么答案就是匹配的括号个数。具体来讲，对于一个长度为 $x$ 的落单棍子，我们在 $x$ 处放一个左括号；对于一对长度为 $x$ 的棍子，我们在 $2x-1$ 处放一个右括号。需要注意的是，如果一个位置同时有左右括号，那么我们让左括号放在前面。（这个也可以直接将下标翻倍来解决）

这样静态问题就做完了。

带修改怎么做呢？其实很简单，对于一个位置的修改只会影响至多两个位置的括号个数，所以我们用线段树来维护每个位置的括号匹配情况。具体做法是，对于一个括号序列，我们先将能匹配的括号删去。例如，))())(()( 可以被删成 )))((。容易发现被删去之后的括号序列一定是形如 ))...)((...( 的形式。我们对于线段树上每个节点维护被删去之后的左括号数、右括号数和匹配的括号对数，pushup 时就是将左儿子的右括号和右儿子的左括号匹配一下就行了。

然后就做完了，时间复杂度 $O(n\log n)$，可能会带 $2$ 或 $4$ 的常数。

代码很短。

#include <bits/stdc++.h>

typedef long long LL;

const int N = 2e5 + 5;

int n, Q;
LL a[N];

struct SegValue {
	LL pre, suf, match;
};
SegValue calc(const SegValue &x, const SegValue &y) {
	SegValue z;
	LL val = std::min(x.suf, y.pre);
	z.match = x.match + y.match + val;
	z.pre = x.pre + (y.pre - val);
	z.suf = (x.suf - val) + y.suf;
	return z;
}
struct SegmentTree {
	SegValue t[N << 4];
	void modify(int qind, const SegValue &qv, int x = 1, int l = 1, int r = 4 * n) {
		if(l == r) { t[x] = qv; return; }
		int mid = (l + r) >> 1;
		if(qind <= mid) modify(qind, qv, x << 1, l, mid);
		else modify(qind, qv, x << 1 | 1, mid + 1, r);
		t[x] = calc(t[x << 1], t[x << 1 | 1]);
	}
	SegValue query() { return t[1]; }
} seg;

int main() {
	scanf("%d%d", &n, &Q);
	LL even = 0;
	for(int i = 1; i <= n; i++) {
		scanf("%lld", &a[i]);
		if(a[i] & 1) seg.modify(2 * i - 1, {0, 1, 0});
		seg.modify(4 * i - 2, {a[i] >> 1, 0, 0}), even += a[i] >> 1;
	}
	while(Q--) {
		int p, x;
		scanf("%d%d", &p, &x);
		even -= a[p] >> 1;
		a[p] += x;
		even += a[p] >> 1;
		seg.modify(2 * p - 1, {0, a[p] & 1, 0});
		seg.modify(4 * p - 2, {a[p] >> 1, 0, 0});
		LL match = seg.query().match;
		printf("%lld\n", match + (even * 2 - 2 * match) / 3);
	}
	return 0;
}