题解：三角形集合问题（CCO 2023 Day2 T3）

一、题目核心分析

1. 问题本质

给定 $N$ 种长度的棍子（长度 $\ell=1\sim N$，数量 $c_\ell$），支持动态修改棍子数量，每次修改后需计算最多能制作的等腰三角形数量。等腰三角形的定义是：两根长度为 $\ell$ 的棍子 + 一根长度在 $[1, 2\ell-1]$ 之间的棍子（满足三角形不等式）。

2. 关键观察

（1）等腰三角形的两种构成方式

• 类型 A（等边三角形）：三根长度均为 $\ell$ 的棍子。每 3 根可组成 1 个三角形，贡献 $\left\lfloor \frac{c_\ell}{3} \right\rfloor$ 个。
• 类型 B（非等边等腰三角形）：两根长度为 $\ell$ 的棍子 + 一根长度为 $m$（$m \neq \ell$ 且 $1 \leq m \leq 2\ell-1$）的棍子。每 2 根 $\ell$ 棍子可搭配 1 根 $m$ 棍子组成 1 个三角形。

（2）总三角形数量的数学表达

设总三角形数量为 $ans$，则：

$$ans = \frac{1}{3} \left( \text{总棍子数} + \min_{\text{合法分配}} \left( \text{未使用棍子数} \right) \right) $$

• 总棍子数 $sum = \sum_{i=1}^N c_i$，每个三角形消耗 3 根棍子，故 $sum - 3ans$ 为未使用棍子数（非负）。
• 核心是最小化未使用棍子数，即最大化 $ans$。

（3）未使用棍子数的约束

对于每种长度 $\ell$，设 $x_\ell$ 为用于类型 A 的数量（$x_\ell \equiv 0 \pmod{3}$），$y_\ell$ 为用于类型 B 的数量（$y_\ell \equiv 0 \pmod{2}$），则 $x_\ell + y_\ell \leq c_\ell$。未使用棍子数为 $\sum_{i=1}^N (c_\ell - x_\ell - y_\ell)$，需满足类型 B 的搭配约束（$y_\ell$ 对应的 $m$ 存在）。

通过转化，未使用棍子数可表示为一个前缀和的最小值，需用线段树维护。

二、完整代码

#include <bits/stdc++.h>
#define INF 1000000000
#define LINF 1000000000000000000
#define MOD 1000000007
#define mod 998244353
#define F first
#define S second
#define ll long long
#define N 200010
#define M ((1<<19)+10)  // 线段树大小（2^19 足够覆盖 2e5）
using namespace std;

// 线段树节点：s为区间和，v为区间内前缀和的最小值
struct Node {
    ll s, v;
    Node(ll _s = 0, ll _v = 0) {
        s = _s, v = _v;
    }
    // 合并两个节点：左节点 + 右节点
    Node operator + (const Node &x)const {
        return Node(s + x.s, min(v + x.s, x.v));
    }
};

struct SegT {
    ll pre[N];  // 预处理数组，存储每个位置的初始值
    Node val[M];  // 线段树节点数组

    // 构建线段树：x为节点编号，[l, r]为当前区间
    void build(int x, int l, int r) {
        if (l == r) {
            val[x] = Node(pre[l], min(0ll, pre[l]));
            return;
        }
        int mid = (l + r) >> 1, a = x << 1;
        build(a, l, mid);       // 左子树
        build(a | 1, mid + 1, r); // 右子树
        val[x] = val[a] + val[a | 1]; // 合并左右子树
        return;
    }

    // 更新线段树：x为节点编号，l为更新位置，v为变化量，[tl, tr]为当前区间
    void update(int x, int l, int v, int tl, int tr) {
        if (tl == tr) {
            val[x].s += v;       // 更新区间和
            val[x].v = min(0ll, val[x].s); // 更新前缀最小值（仅当前位置，前缀即自身）
            return;
        }
        int mid = (tl + tr) >> 1, a = x << 1;
        if (mid >= l)
            update(a, l, v, tl, mid); // 左子树更新
        else
            update(a | 1, l, v, mid + 1, tr); // 右子树更新
        val[x] = val[a] + val[a | 1]; // 合并更新后的左右子树
        return;
    }
} segt;

int n, q, a[N];  // a[i] 存储长度为i的棍子数量
ll sum = 0;      // 总棍子数

int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        sum += a[i];  // 累加总棍子数
        // 计算pre数组初始值：
        // 1. 长度i的棍子最多能提供 floor(a[i]/2) 个"两根组"（用于类型B）
        // 这些"两根组"可搭配长度≤2i-1的棍子，故贡献到位置 min(n, 2i-1)
        segt.pre[min(n, i * 2 - 1)] += a[i] / 2;
        // 2. 若a[i]为奇数，剩余1根无法组成"两根组"，产生-1的贡献（未使用）
        if (a[i] & 1)
            segt.pre[i]--;
    }
    segt.build(1, 1, n);  // 构建线段树

    while (q--) {
        int x, y;  // x为长度，y为数量变化量
        scanf("%d%d", &x, &y);
        // 第一步：撤销x长度棍子的旧贡献
        segt.update(1, min(n, x * 2 - 1), -a[x] / 2, 1, n);
        if (a[x] & 1)
            segt.update(1, x, 1, 1, n);  // 撤销奇数时的-1贡献

        // 第二步：更新x长度的棍子数量和总棍子数
        a[x] += y;
        sum += y;

        // 第三步：添加x长度棍子的新贡献
        segt.update(1, min(n, x * 2 - 1), a[x] / 2, 1, n);
        if (a[x] & 1)
            segt.update(1, x, -1, 1, n);  // 新奇数时添加-1贡献

        // 计算答案：(总棍子数 + 线段树维护的最小前缀和) / 3
        printf("%lld\n", (sum + segt.val[1].v) / 3);
    }
    return 0;
}

三、关键逻辑详解

1. 预处理数组 pre 的设计

pre[i] 是线段树的核心维护对象，其值由两部分组成：

• 正贡献（类型 B 潜力）：对于长度 $\ell$，每 2 根棍子可组成 1 个“两根组”（用于类型 B），该“两根组”可搭配长度 $\leq 2\ell-1$ 的棍子。因此，将 $\left\lfloor \frac{c_\ell}{2} \right\rfloor$ 累加到 pre[min(n, 2ℓ-1)]（表示该“两根组”对所有 $\leq 2\ell-1$ 的长度均有效）。
• 负贡献（未使用棍子）：若 $c_\ell$ 为奇数，剩余 1 根棍子无法组成“两根组”或“三根组”，会成为未使用棍子，故在 pre[ℓ] 中减去 1。

2. 线段树的维护逻辑

线段树的每个节点存储两个值：

• s：当前区间的 pre 数组和；
• v：当前区间内的前缀和最小值（前缀和从左到右累加，取最小值）。

线段树的合并规则（operator+）：

• 合并左节点 L 和右节点 R 时，总区间和为 L.s + R.s；
• 总区间的前缀最小值为 min(L.v + R.s, R.v)：
  • L.v + R.s：左区间的最小前缀和 + 右区间的总和（表示左区间前缀延伸到右区间的所有位置）；
  • R.v：右区间自身的最小前缀和。

3. 动态更新流程

每次修改长度 $\ell$ 的棍子数量时，需分三步：

1. 撤销旧贡献：减去该长度之前在 pre 数组中的正贡献和负贡献；
2. 更新数量：修改 a[ℓ] 和总棍子数 sum；
3. 添加新贡献：根据更新后的 a[ℓ] 重新计算并添加正贡献和负贡献。

4. 答案计算

最终答案为：

$$ans = \frac{sum + segt.val[1].v}{3}$$

• sum 是总棍子数；
• segt.val[1].v 是整个数组的前缀和最小值，对应“最小未使用棍子数”；
• 除以 3 是因为每个三角形消耗 3 根棍子。

四、样例解析

样例输入

4 3
3 1 4 1
3 -3
1 6
2 1

初始状态

• 长度 1：$c_1=3$ → 正贡献 $\lfloor 3/2 \rfloor=1$（加到 pre[1]，因 $2×1-1=1$），奇数负贡献 $-1$（pre[1] 变为 $1-1=0$）；
• 长度 2：$c_2=1$ → 正贡献 $\lfloor 1/2 \rfloor=0$（加到 pre[3]，因 $2×2-1=3$），奇数负贡献 $-1$（pre[2] 变为 $-1$）；
• 长度 3：$c_3=4$ → 正贡献 $\lfloor 4/2 \rfloor=2$（加到 pre[4]，因 $2×3-1=5$，取 min(4,5)=4），偶数无负贡献（pre[3] 不变）；
• 长度 4：$c_4=1$ → 正贡献 $\lfloor 1/2 \rfloor=0$（加到 pre[4]，因 $2×4-1=7$，取 min(4,7)=4），奇数负贡献 $-1$（pre[4] 变为 $2+0-1=1$）；
• 总棍子数 $sum=3+1+4+1=9$；
• 线段树维护的前缀和最小值为 $\min(0, -1, -1, 1) = -1$；
• 初始答案为 $(9 + (-1))/3 = 8/3=2$（但样例初始无输出，首次修改后计算）。

第一次修改（3 -3）

• 长度 3 的棍子数量变为 $4-3=1$；
• 撤销旧贡献：减去 2（pre[4] 减 2）；
• 添加新贡献：正贡献 $\lfloor 1/2 \rfloor=0$（pre[4] 加 0），奇数负贡献 $-1$（pre[3] 减 1）；
• 总棍子数 $sum=9-3=6$；
• 前缀和最小值为 $\min(0, -1, -2, 0) = -2$；
• 答案：$(6 + (-2))/3 = 4/3=1$（与样例一致）。

后续修改同理，最终答案均符合样例输出。

五、复杂度分析

• 时间复杂度：$O(N \log N + Q \log N)$。线段树的构建和每次更新、查询均为 $O(\log N)$，适配 $N, Q \leq 2×10^5$ 的数据范围。
• 空间复杂度：$O(N + 4×M)$。pre 数组占用 $O(N)$，线段树占用 $O(4×M)$（$M=2^{19}$ 足够覆盖 $2×10^5$）。

总结

本题的核心是将“最大化等腰三角形数量”转化为“最小化未使用棍子数”，通过数学建模将约束条件转化为前缀和最小值问题，再用线段树高效维护动态更新。关键在于：

1. 准确拆分两种类型的三角形贡献；
2. 设计 pre 数组和线段树节点，巧妙维护前缀和最小值；
3. 动态更新时正确撤销和添加贡献，确保计算准确。