P10071 [CCO2023] Triangle Collection 简要题解

· · 题解

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

首先考虑每种长度的棍子都只有偶数根的情况，那么答案就是总棍子数除以 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;
}