题解：P10071 [CCO2023] Triangle Collection

第一次做题解，有~~亿~~些紧张 先来做静态问题，即不带修改。 首先考虑每种长度的棍子都只有偶数根的情况，那么答案就是总棍子数除以 3 3 下取整。显然答案不会大于这个数，下面构造地证明答案不会小于这个数： 由于所有长度的棍子都是偶数根，所以我们把两根同样长的棍子打包成 一对 棍子。显然不会出现落单的棍子。 如果我们任取 3 3 对棍子，长度分别为 a , b , c ( a ≤ b ≤ c ) a,b,c(a≤b≤c)，那么可以构造两个三角形： ( a , b , b ) (a,b,b) 和 ( a , c , c ) (a,c,c)。容易验证满足题目条件。 重复以上操作，最后棍子只会剩下最多两对。如果最后剩 0 0 对或 1 1 对，那么显然不能做出新的三角形了，此时总棍子数为 6 k 6k 或 6 k + 2 6k+2 的形式（其中 k k 为进行上面操作的次数），除以 3 3 下取整正好是 2 k 2k，满足我们的结论；如果最后剩 2 2 对，假设长度为 a , b ( a ≤ b ) a,b(a≤b)，那么我们可以再构造出一个三角形 a , b , b a,b,b，也满足结论。 现在考虑如果出现奇数根棍子怎么办。我们还是将两根相同的棍子打包成 一对，那么此时会出现若干 落单 的棍子。显然这些落单的棍子只能作为底边和另外一对棍子凑成一个三角形。此时我们的最优策略是贪心地将尽量多的落单棍子做成三角形，然后加上未被做成三角形的那些 对 的答案（即总数除以 3 3 下取整）。下面证明这一点： 因为一个落单的棍子必须依赖另外一对棍子才能被拼成三角形，所以我们来观察没有落单的棍子。当我们把一个落单的棍子做成三角形时，我们会消耗 1 1 对棍子。但是如果不将这根落单的棍子做成三角形，我们则会让那些没落单的棍子内部消化，这时则会消耗 1.5 1.5 对棍子，即 3 3 根棍子。所以尽量多将落单的棍子做成三角形一定是更优的。 如果觉得上面那个证明太感性，也可以用数学计算的方法：假设我们将 x x 根落单的棍子做成了三角形，并且总共有 y y 对棍子，其中 y ≥ x y≥x，那么答案是 x + ⌊ y − 2 x 3 ⌋ = ⌊ x + y 3 ⌋ x+⌊ 3 y−2x ​ ⌋=⌊ 3 x+y ​ ⌋，由于 y y 不会变，所以显然 x x 越大答案越大。 现在的问题就变成了如何让尽量多落单的棍子被做成三角形。这个有一个比较简单的做法。 我们发现如果固定腰的长度，那么底边的长度范围是一段前缀。所以我们可以把腰当成右括号，底边当成左括号，那么答案就是匹配的括号个数。具体来讲，对于一个长度为 x x 的落单棍子，我们在 x x 处放一个左括号；对于一对长度为 x x 的棍子，我们在 2 x − 1 2x−1 处放一个右括号。需要注意的是，如果一个位置同时有左右括号，那么我们让左括号放在前面。（这个也可以直接将下标翻倍来解决） 这样静态问题就做完了。 带修改怎么做呢？其实很简单，对于一个位置的修改只会影响至多两个位置的括号个数，所以我们用线段树来维护每个位置的括号匹配情况。具体做法是，对于一个括号序列，我们先将能匹配的括号删去。例如，))())(()( 可以被删成 )))((。容易发现被删去之后的括号序列一定是形如 ))...)((...( 的形式。我们对于线段树上每个节点维护被删去之后的左括号数、右括号数和匹配的括号对数，pushup 时就是将左儿子的右括号和右儿子的左括号匹配一下就行了。 然后就做完了，时间复杂度 O ( n log ⁡ n ) O(nlogn)，可能会带 2 2 或 4 4 的常数。 不说废话了，上代码 Code _**~~我没写注释，为了方便你们copy~~**_ #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; }