AtCoder Beginner Contest 467 题解

for-each2026年8月18日大约 25 分钟

AtCoder Beginner Contest 467 题解

项目	内容
比赛时间	2026-07-18
比赛链接	https://atcoder.jp/contests/abc467
题目数量	A–G 共 7 题

比赛概览

本场难度从前到后逐渐拉升：A、B 是纯粹入门题；C 与 E 是"同一题意、不同约束"的一对题（C 中 $M=2$ 可直接枚举，E 中 $M$ 可高达 $10^9$ ，需要"候选解集 + 差分更新"的技巧）；D 是计算几何（垂直平分线）；F 是"贪心排序 + 线段树合并"的经典结构题；G 是本场压轴，要求支持区间动态"前 $t$ 大和"查询，需要 merge-sort tree（或 wavelet matrix）一类的数据结构。值得重点掌握的点：E 的"极值一定落在使某一项取模结果为 $0$ 的候选点"思想、F 的合并式线段树 push-up 公式、G 的"索引-值两维对调"技巧。

A - Obesity

题目链接：https://atcoder.jp/contests/abc467/tasks/abc467_a

题目大意

给出身高 $H$ （单位 cm）和体重 $W$ （单位 kg）。按日本标准， $\mathrm{BMI} \ge 25\ \mathrm{kg/m^2}$ 即算肥胖，其中 $\mathrm{BMI} = W \div (\text{身高/米})^2$ 。判断该人是否肥胖，输出 Yes 或 No。输入为一行两个整数 $H\ W$ 。

思路

把身高从厘米换成米： $H\,\mathrm{cm} = \dfrac{H}{100}\,\mathrm{m}$ 。于是

\mathrm{BMI} = \frac{W}{\left(\frac{H}{100}\right)^2} = \frac{10^4 W}{H^2}\ \mathrm{kg/m^2}.

肥胖条件为 $\dfrac{10^4 W}{H^2} \ge 25$ 。关键点：不要用浮点数。虽然本题数据下 $25.0$ 等值能被浮点数精确表示，直接比较也大概率能过，但测试数据里专门准备了浮点写法会 WA 的用例。把不等式两侧交叉相乘，化为整式：

10^4 W \ge 25 H^2 \iff 400W \ge H^2.

只需判断 $400W \ge H^2$ 是否成立。数值非常小（ $H \le 300$ 时 $H^2 \le 90000$ ），int 足够，代码中用 long long 只是习惯性保险。

易错点：判定是" $25$ 或以上"，等号也要输出 Yes，所以用 $\ge$ ； $H,W \ge 1$ ，无需处理除零。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int H, W;
    cin >> H >> W;
    // BMI = W / (H/100)^2 = 10000W / H^2 >= 25  <=>  400W >= H^2
    if (400LL * W >= 1LL * H * H) cout << "Yes\n";
    else cout << "No\n";
    return 0;
}

官方题解给出的 Python 实现：

H, W = map(int, input().split())
if 400 * W >= H * H:
    ans = "Yes"
else:
    ans = "No"
print(ans)

复杂度分析

时间复杂度： $O(1)$
空间复杂度： $O(1)$

B - Keep the Change

题目链接：https://atcoder.jp/contests/abc467/tasks/abc467_b

题目大意

高桥在 $N$ 家店买东西。在第 $i$ 家店，商品价格为 $A_i$ 元，他付了 $B_i$ 元（ $A_i \le B_i$ ）；若 $S_i=$ keep 表示他没要找零，take 表示他收下了找零。问他实际最终钱数比"每家店都收找零"的情形少多少。输入第一行 $N$ ，接下来 $N$ 行每行 A_i B_i S_i。

思路

初始的 $10000$ 元在两种情形（实际做法 vs 全收找零）中是完全相同的起点，可以直接忽略，只比较每笔交易上的差额。

若 $S_i=$ take：他本来就收了找零，与"全收找零"的情形一致，损失 $0$ 。
若 $S_i=$ keep：他没收到找零，而商品价值 $A_i$ 、付款 $B_i$ ，本应找回 $B_i - A_i$ 元，因此损失恰好为 $B_i - A_i$ 。

所以答案就是所有 keep 项的 $B_i - A_i$ 之和：

\sum_{S_i = \texttt{keep}} (B_i - A_i).

逐行读入、用 if 判断字符串即可，与 $N$ 成线性。注意 $B_i - A_i \ge 0$ （题设 $A_i \le B_i$ ），答案不会为负。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    long long ans = 0;
    for (int i = 0; i < N; i++) {
        int A, B;
        string S;
        cin >> A >> B >> S;
        if (S == "keep") ans += B - A;
    }
    cout << ans << '\n';
    return 0;
}

复杂度分析

时间复杂度： $O(N)$
空间复杂度： $O(1)$

C - Adjacent Sums (easy)

题目链接：https://atcoder.jp/contests/abc467/tasks/abc467_c

题目大意

给定整数序列 $A=(A_1,\dots,A_N)$ 与 $B=(B_1,\dots,B_{N-1})$ ，元素都在 $[0,M-1]$ 内。每次操作可以选一个 $i$ 把 $A_i$ 加 $1$ 。求最少操作次数，使对每个 $i$ 都有

(A_i + A_{i+1}) \bmod M = B_i.

本题中 $M=2$ （C 与 E 题意完全相同，仅约束不同，E 中 $3 \le M \le 10^9$ ）。输入第一行 $N\ M$ ，第二行 $A_1\dots A_N$ ，第三行 $B_1\dots B_{N-1}$ 。题目保证一定有解。

思路

记最终序列为 $A'$ 。由于操作只做加法，且判定条件只关心模 $M$ 的余数，把 $A_i$ 变成某个模 $M$ 意义下等于 $A'_i$ 的数所需的最少操作数就是

(A'_i - A_i) \bmod M

（从 $A_i$ 开始不断 $+1$ ，第一次撞到与 $A'_i$ 同余的数所需步数）。

关键观察：条件 $\bigl(A'_i + A'_{i+1}\bigr) \bmod M = B_i$ 是一个首尾相接的递推关系——一旦 $A'_1 \bmod M$ 固定，后面的每个 $A'_i \bmod M$ 都被唯一确定：

A'_{i+1} \equiv B_i - A'_i \pmod M.

因为约束只涉及相邻两项，所以所有合法终态恰好由 $A'_1 \bmod M$ 的取值一一标定。

本题 $M=2$ ， $A'_1$ 只有 $0$ 或 $1$ 两种可能，对这两种情况各做一遍：先按递推推出 $A'_1,\dots,A'_N$ ，再累加 $(A'_i - A_i) \bmod 2$ 得到该情况下的操作数，取两者的较小值即可。总复杂度 $O(NM)=O(2N)$ 。

正确性：递推给出的终态是唯一满足全部相邻和条件的序列；对固定的 $A'_1$ ，达到它所需的最小操作数为逐项 $(A'_i-A_i)\bmod M$ 之和（各项独立，互不影响）。枚举所有 $A'_1$ 的取值即覆盖全部合法终态。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, M;
    cin >> N >> M; // 本题恒有 M = 2
    vector<int> A(N), B(N - 1);
    for (int i = 0; i < N; i++) cin >> A[i];
    for (int i = 0; i < N - 1; i++) cin >> B[i];

    const int INF = 1 << 30;
    int ans = INF;
    for (int s = 0; s < M; s++) {          // 枚举 A'_1 的取值
        vector<int> C(N);
        C[0] = s;
        for (int i = 0; i + 1 < N; i++) {
            C[i + 1] = ((B[i] - C[i]) % M + M) % M;   // 递推确定后面的值
        }
        int cost = 0;
        for (int i = 0; i < N; i++) {
            cost += ((C[i] - A[i]) % M + M) % M;      // 该位置所需操作数
        }
        ans = min(ans, cost);
    }
    cout << ans << '\n';
    return 0;
}

复杂度分析

时间复杂度： $O(NM) = O(N)$ （因 $M=2$ ）
空间复杂度： $O(N)$

D - Concentric Circles

题目链接：https://atcoder.jp/contests/abc467/tasks/abc467_d

题目大意

问平面上是否存在两个圆 $C_1,C_2$ （可以重合）满足： $C_1$ 的圆周经过两个不同点 $P,Q$ ， $C_2$ 的圆周经过两个不同点 $R,S$ ，且 $C_1$ 与 $C_2$ 圆心相同。给出 $T$ 个测试用例，每个给出 $P_x\ P_y\ Q_x\ Q_y\ R_x\ R_y\ S_x\ S_y$ （均为整数， $|坐标| \le 10^9$ ），输出 Yes 或 No。

思路

关键转化：不要去研究圆本身，而是研究圆心能落在哪里。

设 $C_1,C_2$ 的公共圆心为 $O$ 。因为 $P,Q$ 都在 $C_1$ 上，必须有 $OP = OQ$ ，即 $O$ 到 $P,Q$ 等距；到两个定点等距的点的轨迹是线段 $PQ$ 的垂直平分线，记为 $L_1$ 。同理 $O$ 必须在 $R,S$ 的垂直平分线 $L_2$ 上。反过来，只要存在一点 $O$ 同时在 $L_1,L_2$ 上，以 $O$ 为圆心、 $OP$ 为半径作圆即可得到满足条件的 $C_1$ ，以 $O$ 为圆心、 $OR$ 为半径作圆即可得到 $C_2$ 。

所以原问题等价于：

线段 $PQ$ 的垂直平分线 $L_1$ 与线段 $RS$ 的垂直平分线 $L_2$ 是否相交？

利用直线的基本事实：不平行的两条直线必相交；两条不同的平行直线不相交。因此：

$L_1,L_2$ 不平行 $\Rightarrow$ 一定相交，答案为 Yes；
$L_1,L_2$ 平行 $\Rightarrow$ 重合则答案为 Yes，否则 No。

剩下的问题是：如何判定两条垂直平分线的平行与重合，而且要避免浮点误差（坐标可达 $10^9$ ，用浮点判断两线相交很容易出错）。

用整数系数直线方程。 $L_1$ 上任一点 $(x,y)$ 满足 $OP^2 = OQ^2$ ：

(x-P_x)^2+(y-P_y)^2 = (x-Q_x)^2+(y-Q_y)^2,

展开化简得

2(Q_x-P_x)\,x + 2(Q_y-P_y)\,y + P_x^2+P_y^2 - Q_x^2 - Q_y^2 = 0.

写成 $a_1 x + b_1 y + c_1 = 0$ ，其中 $a_1,b_1,c_1$ 都是整数；同理可得 $L_2: a_2 x+b_2 y+c_2=0$ 。

平行判定：两直线平行当且仅当法向量 $(a_1,b_1)$ 与 $(a_2,b_2)$ 平行，即叉积

a_1 b_2 - a_2 b_1 = 0.

重合判定：若平行，还需判断两线是否完全重合。直接比较 $a_1=a_2,\ b_1=b_2,\ c_1=c_2$ 不够，因为系数可以整体缩放（例如 $(a,b,c)=(1,2,3)$ 与 $(2,4,6)$ 表示同一条直线）。解决办法是给直线做规范化（normal form）：对 $ax+by+c=0$ ，要求 $a,b,c$ 为整数、 $\gcd(a,b,c)=1$ 、 $a>0$ （若 $a=0$ 则要求 $b>0$ ）。同一条整数系数直线恰好对应唯一的规范型，于是规范后直接比较三个数即可。

注意叉积 $a_1 b_2$ 两个因子的绝对值都可能达到 $4 \times 10^9$ ，乘积会超过 long long 上限，代码中用 __int128 计算叉积（或者退化为用原始向量 $(Q-P)$ 与 $(S-R)$ 判平行）。另外 $\gcd$ 需用 std::gcd（C++17，能正确处理负数、返回非负值），且 $P \ne Q$ 保证 $(a,b)$ 不全为 $0$ ，规范化的除法不会出问题。

易错点：题目说 $C_1,C_2$ 可以重合，对应两条垂直平分线重合的情形（此时有无数个合法圆心），不要漏判成 No。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// 将直线 ax + by + c = 0 化为标准型：gcd(a,b,c)=1，且 a>0（若 a=0 则 b>0）
tuple<ll, ll, ll> canonical(ll px, ll py, ll qx, ll qy) {
    ll a = 2 * (qx - px);
    ll b = 2 * (qy - py);
    ll c = px * px + py * py - qx * qx - qy * qy;
    ll g = gcd(a, gcd(b, c));
    a /= g; b /= g; c /= g;
    if (a < 0) { a = -a; b = -b; c = -c; }
    if (a == 0 && b < 0) { b = -b; c = -c; }
    return {a, b, c};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        ll px, py, qx, qy, rx, ry, sx, sy;
        cin >> px >> py >> qx >> qy >> rx >> ry >> sx >> sy;
        auto [a1, b1, c1] = canonical(px, py, qx, qy);
        auto [a2, b2, c2] = canonical(rx, ry, sx, sy);
        if ((__int128)a1 * b2 - (__int128)a2 * b1 == 0) {
            // 平行：重合则 Yes，否则 No
            cout << (a1 == a2 && b1 == b2 && c1 == c2 ? "Yes" : "No") << '\n';
        } else {
            cout << "Yes\n";
        }
    }
    return 0;
}

复杂度分析

时间复杂度：每个用例 $O(1)$ （仅常数次整数运算与 $\gcd$ ）
空间复杂度： $O(1)$

E - Adjacent Sums (hard)

题目链接：https://atcoder.jp/contests/abc467/tasks/abc467_e

题目大意

与 C 完全相同，但 $3 \le M \le 10^9$ 、 $2 \le N \le 2 \times 10^5$ ：给定 $A=(A_1,\dots,A_N)$ 、 $B=(B_1,\dots,B_{N-1})$ （元素都在 $[0,M-1]$ ），每次操作把某个 $A_i$ 加 $1$ ，求最小操作数使 $(A_i+A_{i+1}) \bmod M = B_i$ 对每个 $i$ 成立。

思路

C 的做法（枚举 $A'_1$ ）在 $M$ 很大时失效了—— $A'_1$ 有 $M$ 种取值，无法全部枚举。本解法分为两步：先证明最优只可能出现在至多 $N$ 个"候选点"上，再用差分更新在 $O(N\log N)$ 内求出这些候选点的函数值。

第一步：把目标终态参数化。

设最终序列为 $A'$ 。引入辅助序列 $C$ ：

C_1 = 0, \qquad C_{i+1} = B_i - C_i \pmod M.

那么递推关系 $(A'_i+A'_{i+1}) \bmod M = B_i$ 的通解是

A'_i \equiv C_i + (-1)^{i+1} s \pmod M,

其中 $s = A'_1 \bmod M$ 是自由参数。验证（归纳）： $i=1$ 时 $A'_1 = C_1 + s = s$ 成立；若 $A'_i \equiv C_i + (-1)^{i+1}s$ ，则

A'_{i+1} \equiv B_i - A'_i \equiv (C_{i+1}+C_i) - C_i - (-1)^{i+1}s = C_{i+1} + (-1)^{i+2}s. \qquad\blacksquare

记 $D_i = C_i - A_i$ 。把 $A_i$ 变成与 $A'_i$ 同余的数所需步数为 $(A'_i-A_i)\bmod M$ ，于是总操作数

g(s) = \sum_{i=1}^{N} \Bigl(D_i + (-1)^{i+1}s\Bigr) \bmod M,

其中 $(-1)^{i+1} = +1$ （ $i$ 奇）或 $-1$ （ $i$ 偶）， $0 \le s < M$ 。问题化为：在 $s=0,1,\dots,M-1$ 中最小化 $g(s)$ 。

第二步：候选解集定理。

使得 $g(s)$ 取到最小值的 $s$ 中，至少存在一个 $s$ ，满足对某个 $i$ 有 $\bigl(D_i + (-1)^{i+1}s\bigr) \bmod M = 0$ 。

证明思路（官方题解）：在所有使 $g$ 最小的 $s$ 中，取一个使 $\min_i f_i(s)$ 最小的 $s'$ （ $f_i(s)=\bigl(D_i+(-1)^{i+1}s\bigr)\bmod M$ ）。反设所有 $f_i(s')>0$ 。考察 $s'+1$ 与 $s'-1$ （模 $M$ ）两个邻居：当 $s$ 增加 $1$ 时，奇数项 $+1$ 、偶数项 $-1$ （个别项越过 $0\leftrightarrow M-1$ 的边界除外），因此两个方向中必有某一方向使 $g$ 严格变小，或使 $g$ 不变而 $\min_i f_i$ 变小，均与 $s'$ 的取法矛盾。故存在 $f_i(s')=0$ 。

也可以用几何视角理解：在相邻两个候选点之间没有 $f_i$ 为 $0$ ，此时不会出现偶数项的"从 $0$ 越界到 $M-1$ "，只有奇数项在 $s=$ （奇数候选点） $-1$ 处发生 $M-1\to 0$ 的越界。于是区间内部 $g$ 的"斜率"（相邻差值）随 $s$ 增大而单调不增， $g$ 在区间内是（离散）凹的，最小值一定落在区间端点——即候选点处。把 $s=0$ 也加入候选集以处理环上的拼接。

候选点的具体形态：奇数 $i$ 使 $f_i(s)=0$ 的 $s$ 满足 $s \equiv -D_i$ ；偶数 $i$ 满足 $s \equiv D_i$ 。故候选集

\{0\} \cup \{(-D_i)\bmod M : i \text{ 奇}\} \cup \{D_i \bmod M : i \text{ 偶}\}

的大小至多为 $N+1$ 。

第三步：差分求值。

在候选点之外，我们还差一个工具：对任意候选 $s$ 快速求 $g(s)$ 。观察当 $s$ 增加 $1$ 时每项的变化：

奇数项 $f_i(s) = (D_i+s)\bmod M$ ：一般 $+1$ ；但当 $f_i(s)=M-1$ 时越界到 $0$ ，实际变化为 $-(M-1)$ ，相比正常变化多了 $-M$ 。
偶数项 $f_i(s) = (D_i-s)\bmod M$ ：一般 $-1$ ；但当 $f_i(s)=0$ 时越界到 $M-1$ ，实际变化为 $+(M-1)$ ，相比正常变化多了 $+M$ 。

记 $\#\text{odd}$ 、 $\#\text{even}$ 分别为奇数/偶数下标个数，则从 $s$ 到 $s+1$ 的差分为

g(s+1)-g(s) = \#\text{odd} - \#\text{even} - M\cdot \#\{\text{奇数项在 }s\text{ 越界}\} + M\cdot \#\{\text{偶数项在 }s\text{ 越界}\}.

奇数项的越界点（ $f_i=M-1$ ）为 $s \equiv M-1-D_i$ ，偶数项的越界点（ $f_i=0$ ）为 $s \equiv D_i$ 。这些越界事件总共恰好 $N$ 个。

于是算法为：先算出 $g(0)=\sum_i (D_i \bmod M)$ ；把所有候选 $s$ 排序去重；把 $N$ 个越界事件按 $s$ 排序。然后从小到大地扫过每个候选点：从当前点 $cur$ 走到下一个候选点 $t$ ，先按基础斜率 $\#\text{odd}-\#\text{even}$ 累加 $(t-cur)$ 步，再把越界点落在 $[cur,t)$ 内的所有事件修正量（ $-M$ 或 $+M$ ）加进去。排序是瓶颈，总复杂度 $O(N\log N)$ 。

易错点： $C_i$ 是 $B$ 的交错和，绝对值可达 $O(NM)\approx 2\times 10^{14}$ ， $D_i$ 同理，务必用 long long 并在取模处统一写成 (x % M + M) % M 得到非负余数；修正量是 $\pm M$ 而非 $\pm(M-1)$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    ll M;
    cin >> N >> M;
    vector<ll> A(N + 1), B(N);
    for (int i = 1; i <= N; i++) cin >> A[i];
    for (int i = 1; i <= N - 1; i++) cin >> B[i];

    auto norm = [&](ll x) {
        x %= M;
        if (x < 0) x += M;
        return x;
    };

    // C_1 = 0, C_{i+1} = B_i - C_i, D_i = C_i - A_i
    vector<ll> C(N + 1, 0), D(N + 1);
    for (int i = 1; i <= N - 1; i++) C[i + 1] = B[i] - C[i];

    vector<ll> cands = {0};                 // 候选 s 的集合
    vector<pair<ll, ll>> events;            // (越界点 s, 修正量)
    ll g0 = 0;                              // g(0)
    int cntOdd = 0, cntEven = 0;
    for (int i = 1; i <= N; i++) {
        D[i] = C[i] - A[i];
        g0 += norm(D[i]);
        if (i & 1) {
            cntOdd++;
            cands.push_back(norm(-D[i]));                // 奇数项 f_i 归零
            events.push_back({norm(M - 1 - D[i]), -M});  // 奇数项从 M-1 越界到 0
        } else {
            cntEven++;
            cands.push_back(norm(D[i]));                 // 偶数项 f_i 归零
            events.push_back({norm(D[i]), +M});          // 偶数项从 0 越界到 M-1
        }
    }

    sort(cands.begin(), cands.end());
    cands.erase(unique(cands.begin(), cands.end()), cands.end());
    sort(events.begin(), events.end());

    ll base = cntOdd - cntEven;
    ll cur = 0, g = g0, ans = (1LL << 62);
    int ptr = 0;
    for (ll t : cands) {
        g += base * (t - cur);                            // 正常斜率部分的累计
        while (ptr < (int)events.size() && events[ptr].first < t) {
            g += events[ptr].second;                      // 越界事件的修正
            ptr++;
        }
        ans = min(ans, g);
        cur = t;
    }
    cout << ans << '\n';
    return 0;
}

复杂度分析

时间复杂度： $O(N\log N)$ （排序候选集与事件是瓶颈，差分扫一遍为 $O(N)$ ）
空间复杂度： $O(N)$

F - Email Scheduling Optimization

题目链接：https://atcoder.jp/contests/abc467/tasks/abc467_f

题目大意

给 $N$ 家公司发邮件并等回复。给第 $j$ 家公司写邮件耗时 $A_j$ 分钟，发出后 $B_j$ 分钟后收到回复。他从时间 $0$ 开始，按任意顺序一封一封地写（不能同时写），发信本身不耗时。求使得所有回复都收到的最早时间。

现在有 $Q$ 次修改：1 i x 把 $A_i$ 改为 $x$ ，或 2 i x 把 $B_i$ 改为 $x$ 。每次修改后都要重新输出答案。 $N,Q \le 10^5$ ， $A_j,B_j,x \le 10^9$ 。

思路

第一步：最优顺序是固定的——按 $B$ 从大到小写。

证明（交换论证）：假设某最优顺序中出现相邻两项 $P_i,P_{i+1}$ 满足 $B_{P_i} < B_{P_{i+1}}$ 。设他们开始前已累计书写时间 $S$ 。交换前这两项收到回复的时刻分别为

S + A_{P_i} + B_{P_i}, \qquad S + A_{P_i} + A_{P_{i+1}} + B_{P_{i+1}},

因为 $A_{P_{i+1}} \ge 1$ 且 $B_{P_{i+1}} > B_{P_i}$ ，前者严格小于后者，故交换前这两项带来的最大时刻为 $S + A_{P_i}+A_{P_{i+1}}+B_{P_{i+1}}$ 。交换后两项对应的最大时刻为

\max\bigl(S + A_{P_{i+1}} + B_{P_{i+1}},\ S + A_{P_{i+1}}+A_{P_i}+B_{P_i}\bigr),

两项都不超过交换前的那个值（第一项少了 $A_{P_i}$ ，第二项的 $B$ 更小），所以交换不会让答案变差。反复交换直到 $B$ 降序排列，故按 $B$ 降序写一定最优； $B$ 相同则顺序无关。

第二步：把"按 $B$ 降序处理"抽象成线段树的合并。

若把一个公司看作"叶节点"，一段公司按 $B$ 降序排好后，这段的收尾时刻可以用两个量刻画：

sum：这段所有 $A$ 之和（写完整段所需总时间）；
ans：从时刻 $0$ 开始写这段时，最晚收到回复的时刻。

单个公司（写 $A_j$ 分钟，回复 $B_j$ 分钟后到）：sum = A_j，ans = A_j + B_j。

两段 $L$ （ $B$ 更大）接 $R$ （ $B$ 更小）合并时，先写 $L$ 再写 $R$ ， $R$ 内的时间整体平移 sum(L)，于是

\text{sum}(L\cup R) = \text{sum}(L) + \text{sum}(R), \qquad \text{ans}(L\cup R) = \max\bigl(\text{ans}(L),\ \text{sum}(L)+\text{ans}(R)\bigr).

根节点的 ans 就是答案。

第三步：处理修改——按 $B$ 坐标压缩建树。

把所有可能出现过的 $B$ 值（初始 $B_j$ 与所有 2 i x 里的 $x$ ）收集起来去重，按降序排列，作为线段树的"位置"：位置越靠左， $B$ 越大，正好对应最优书写顺序。每个位置（叶子）存下"当前 $B$ 等于该值的所有公司"的 $A$ 之和；同 $B$ 的公司顺序任意，叶子内最晚回复时刻为 sum + B（由最后一个写完的公司决定）。

类型 1（改 $A_i$ ）：公司 $i$ 所在位置不变，叶子 sum 减去旧 $A_i$ 、加上新 $x$ ；
类型 2（改 $B_i$ ）：把公司 $i$ 从旧位置移除（sum -= A_i），插入到新 $B$ 对应的位置（sum += A_i），并更新新位置的 leafB。

每次改动后沿叶子向上用上面的合并公式重算，根节点即答案。空叶子用身份元 $(\text{sum}=0,\ \text{ans}=-\infty)$ ，保证合并公式正确。

易错点：修改 2 i x 时若 $x$ 恰好等于当前 $B_i$ 应跳过，避免在同一个叶子上先减后加；所有 $B$ 值必须离线预取进坐标，否则新出现的 $B$ 无处安放。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll NEG = -(1LL << 60);

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N >> Q;
    vector<ll> A(N + 1), B(N + 1);
    for (int i = 1; i <= N; i++) cin >> A[i];
    for (int i = 1; i <= N; i++) cin >> B[i];

    struct Query { int type, i; ll x; };
    vector<Query> qs(Q);
    vector<ll> allB;
    for (int i = 1; i <= N; i++) allB.push_back(B[i]);
    for (int q = 0; q < Q; q++) {
        int t, i; ll x;
        cin >> t >> i >> x;
        qs[q] = {t, i, x};
        if (t == 2) allB.push_back(x);
    }

    sort(allB.begin(), allB.end());
    allB.erase(unique(allB.begin(), allB.end()), allB.end());
    int U = (int)allB.size();

    // 位置越靠左，B 越大
    auto posDesc = [&](ll b) {
        int p = int(lower_bound(allB.begin(), allB.end(), b) - allB.begin());
        return U - 1 - p;
    };

    int SZ = 1;
    while (SZ < U) SZ <<= 1;

    vector<ll> sum(2 * SZ, 0), ans(2 * SZ, NEG);
    vector<ll> leafB(SZ, 0), initSum(SZ, 0);
    vector<int> pos(N + 1);

    for (int i = 1; i <= N; i++) {
        int p = posDesc(B[i]);
        pos[i] = p;
        leafB[p] = B[i];
        initSum[p] += A[i];
    }

    // 合并式 push-up：左孩子 B 更大，先写；右孩子在其 sum 之后开始
    auto pull = [&](int v) {
        sum[v] = sum[2 * v] + sum[2 * v + 1];
        ans[v] = max(ans[2 * v], sum[2 * v] + ans[2 * v + 1]);
    };

    for (int p = 0; p < U; p++) {
        sum[SZ + p] = initSum[p];
        ans[SZ + p] = (initSum[p] > 0 ? initSum[p] + leafB[p] : NEG);
    }
    for (int p = U; p < SZ; p++) {
        sum[SZ + p] = 0;
        ans[SZ + p] = NEG;
    }
    for (int v = SZ - 1; v >= 1; v--) pull(v);

    auto setLeaf = [&](int p, ll newSum) {
        int v = SZ + p;
        sum[v] = newSum;
        ans[v] = (newSum > 0 ? newSum + leafB[p] : NEG);
        for (v >>= 1; v >= 1; v >>= 1) pull(v);
    };

    for (auto& q : qs) {
        if (q.type == 1) {
            int i = q.i;
            setLeaf(pos[i], sum[SZ + pos[i]] - A[i] + q.x);
            A[i] = q.x;
        } else {
            int i = q.i;
            if (q.x != B[i]) {
                int pOld = pos[i], pNew = posDesc(q.x);
                setLeaf(pOld, sum[SZ + pOld] - A[i]);
                leafB[pNew] = q.x;
                setLeaf(pNew, sum[SZ + pNew] + A[i]);
                pos[i] = pNew;
                B[i] = q.x;
            }
        }
        cout << ans[1] << '\n';
    }
    return 0;
}

复杂度分析

时间复杂度： $O\bigl((N+Q)\log(N+Q)\bigr)$ （每次修改单点更新、向上合并 $O(\log)$ 层）
空间复杂度： $O(N+Q)$

G - Many Sweets Problem

题目链接：https://atcoder.jp/contests/abc467/tasks/abc467_g

题目大意

有长度 $N$ 的正整数序列 $A$ 。 $Q$ 次查询，每次格式为 c x l r k：先把 $A_c$ 改为 $x$ ，然后回答子问题——区间 $[l,r]$ 内的糖果美味度依次为 $A_l,\dots,A_r$ ，你可以任选其中若干个吃掉，使总美味度至少为 $k$ ，问最少吃几颗；若无论如何凑不够 $k$ 输出 $-1$ 。 $N,Q \le 10^5$ ， $A_i,x \le 10^9$ ， $k \le 10^{15}$ 。

思路

先明确子问题的答案：为了让吃的颗数最少，当然优先吃美味度大的糖果，所以答案是"最小的 $t$ ，使得 $[l,r]$ 中最大的 $t$ 个元素之和 $\ge k$ "。这是一个典型的动态区间"前 $t$ 大和"查询，难点在于每次查询前还有单点修改。

静态版本的一个自然想法（会 TLE）。 对静态 $A$ 建按下标分段的 merge-sort tree（每节点存区间内元素按值升序 + 前缀和），然后二分阈值 $x$ ，用 $O(\log N)$ 个节点各一次二分判断"值 $\ge x$ 的元素和是否 $\ge k$ "。每步判定 $O(\log^2 N)$ ，外层二分再乘 $\log$ ，达到 $O(\log^3 N)$ 每次查询——官方题解明确说明这样会 TLE。

正解：把 merge-sort tree 的"索引—值"两个维度对调。

普通 merge-sort tree 是"按索引分段建树、节点内按值排序"。我们把它反过来：按值域分段建树（值域线段树），每个节点内存放"值落在该节点值域内"的下标，按下标有序排列。官方题解给出的例子（ $A=(1,6,5,4,9,8,2,7)$ ）：

[1 6 5 4 9 8 2 7]
[1 5 4 2] | [6 9 8 7]
[1 2] | [5 4] | [6 7] | [9 8]
[1] [2] [4] [5] [6] [7] [8] [9]

最底层是按值划分的叶子（值 $1,2,4,5,6,7,8,9$ ），每一层的每个节点内部都按下标排好了序。这带来一个关键性质：对于任意查询下标区间 $[l,r]$ ，在该树任意一个节点的有序列表里， $[l,r]$ 内的元素恰好构成一段连续子数组（按下标连续）。于是可以用"从根往下走"的方式回答子问题：

当前节点覆盖一个值域；它右儿子的值都更大（更甜）。
用二分定位右儿子列表里下标落在 $[l,r]$ 的子数组，得到其中当前激活糖果的个数 cntR 与美味度总和 sumR。
若 $sumR \ge k$ ：光吃右儿子就能凑够，进入右儿子继续；
否则：右儿子全部吃掉（eatCnt += cntR，k -= sumR），进入左儿子继续。

到达叶子（值 $v$ ）时，该值域只剩单一值 $v$ ，由不变式可知 $v\cdot cnt \ge k$ ，故只需再吃 $\left\lceil \dfrac{k}{v}\right\rceil$ 颗。最初还要检查 $[l,r]$ 的总和是否 $\ge k$ ，不足则输出 $-1$ 。

每层只做一次"二分定位 + 区间求和"，共 $O(\log N)$ 层，一次查询 $O(\log^2 N)$ 。

如何支持修改？——离线预取所有可能值，节点存静态二元组，Fenwick 记录"激活"。

由于所有可能出现的值（初始 $A_i$ 与所有查询里的 $x$ ）可以离线预知，我们把每个二元组 $(c, v)$ （下标 $c$ 可能取值 $v$ ）预先放入值树的所有相关节点（值 $v$ 对应的叶子及其全部祖先），并按"先下标后值"排序。每个节点再挂两个 Fenwick：一个记录个数、一个记录总和，只统计"当前激活"的二元组（即下标 $c$ 当前取值恰为该值的那一个）。

初始化：对每个 $i$ ，把 $(i, A_i)$ 在值树上路径的所有节点处 +1 / +A_i。
修改 $A_c: v \to x$ ：把 $(c,v)$ 在路径上全部 -1 / -A_c，再把 $(c,x)$ 在路径上全部 +1 / +x。
查询某节点内下标在 $[l,r]$ 的激活个数/总和：在该节点有序列表中用 lower_bound 定位 $[l,r]$ 的连续段（由于按下标排序，二分找第一个 $\ge l$ 与第一个 $>r$ 的位置即可），再对两个 Fenwick 做区间查询。

之所以可以这样做，是因为一个下标 $c$ 在同一个节点里可能对应多个不同值的二元组，但同一时刻至多有一个被激活（就是它当前的值），Fenwick 里未激活的贡献为 $0$ ，区间求和自动只算激活的那一个。这个技巧与官方题解"索引-值对调"完全等价：树按值划分，把"动态的激活状态"交给 Fenwick 管理。

修改 $O(\log N)$ 个节点、每个节点一次二分一次 Fenwick 更新，为 $O(\log^2 N)$ ；查询同理 $O(\log^2 N)$ 。

正确性要点：下走过程中始终保持不变式"当前节点值域内、 $[l,r]$ 中的激活糖果总和 $\ge k$ "。初始时由总和检查保证；若右儿子总和 $\ge k$ 则进入右儿子（不变式保持）；否则右儿子全部吃掉后剩余 $k' = k - sumR > 0$ ，而左儿子总和 = 当前总和 $- sumR \ge k - sumR = k'$ ，不变式保持。于是叶子处必然 $v\cdot cnt \ge k$ ， $\lceil k/v\rceil$ 有意义且不超过 cnt。

实现注意：值树要用值坐标压缩（ $V \le N+Q$ ）；entries 的总规模是 $O((N+Q)\log(N+Q))$ ，注意内存；Fenwick 用 long long 存总和、个数用 long long 亦无妨；每节点内的二分用 pair<int,int> 比较，查询区间时用 (l,-1)、(r+1,-1) 作哨兵即可。

（官方题解还提到 wavelet matrix 是另一种可行实现，尤其对语言/常数敏感的选手更友好；本文按 merge-sort tree 思路给出完整实现。）

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Fenwick {
    int n;
    vector<ll> bit;
    void init(int n_) { n = n_; bit.assign(n + 1, 0); }
    void add(int pos, ll d) {
        for (int x = pos + 1; x <= n; x += x & -x) bit[x] += d;
    }
    ll sumPrefix(int pos) const {
        if (pos < 0) return 0;
        ll s = 0;
        for (int x = pos + 1; x > 0; x -= x & -x) s += bit[x];
        return s;
    }
    ll range(int pl, int pr) const {           // [pl, pr)
        return sumPrefix(pr - 1) - sumPrefix(pl - 1);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N >> Q;
    vector<ll> A(N + 1);
    struct Query { int c; ll x; int l, r; ll k; };
    vector<Query> qs(Q);
    vector<ll> xs;

    for (int i = 1; i <= N; i++) { cin >> A[i]; xs.push_back(A[i]); }
    for (int q = 0; q < Q; q++) {
        int c, l, r; ll x, k;
        cin >> c >> x >> l >> r >> k;
        qs[q] = {c, x, l, r, k};
        xs.push_back(x);
    }

    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());
    int V = (int)xs.size();
    vector<ll> valOf(V);
    for (int v = 0; v < V; v++) valOf[v] = xs[v];

    auto idOf = [&](ll v) {
        return int(lower_bound(xs.begin(), xs.end(), v) - xs.begin());
    };

    // 离线预取所有 (下标, 值id) 二元组
    vector<pair<int, int>> pairs;
    for (int i = 1; i <= N; i++) pairs.push_back({i, idOf(A[i])});
    for (auto& q : qs) pairs.push_back({q.c, idOf(q.x)});
    sort(pairs.begin(), pairs.end());
    pairs.erase(unique(pairs.begin(), pairs.end()), pairs.end());

    int SZ = 1;
    while (SZ < V) SZ <<= 1;

    // 值域线段树：每个节点存落在该值域内的 (下标, 值id)，按下标有序
    vector<vector<pair<int, int>>> entries(2 * SZ);
    for (auto& p : pairs) entries[SZ + p.second].push_back(p);

    for (int node = SZ - 1; node >= 1; node--) {
        entries[node].resize(entries[2 * node].size() + entries[2 * node + 1].size());
        merge(entries[2 * node].begin(), entries[2 * node].end(),
              entries[2 * node + 1].begin(), entries[2 * node + 1].end(),
              entries[node].begin());
    }

    vector<Fenwick> fsum(2 * SZ), fcnt(2 * SZ);
    for (int node = 1; node < 2 * SZ; node++) {
        fsum[node].init((int)entries[node].size());
        fcnt[node].init((int)entries[node].size());
    }

    // 激活/撤销某个 (下标, 值) 对在值树上所有祖先处的贡献
    auto activate = [&](int c, ll val, int delta) {
        int vid = idOf(val);
        for (int node = SZ + vid; node >= 1; node >>= 1) {
            auto& ent = entries[node];
            int pos = int(lower_bound(ent.begin(), ent.end(), make_pair(c, vid)) - ent.begin());
            fsum[node].add(pos, delta * val);
            fcnt[node].add(pos, delta);
        }
    };

    for (int i = 1; i <= N; i++) activate(i, A[i], +1);

    // 查询某值树节点内，下标在 [l,r] 且当前激活的 (个数, 总和)
    auto queryRange = [&](int node, int l, int r) {
        auto& ent = entries[node];
        int pl = int(lower_bound(ent.begin(), ent.end(), make_pair(l, -1)) - ent.begin());
        int pr = int(lower_bound(ent.begin(), ent.end(), make_pair(r + 1, -1)) - ent.begin());
        return make_pair(fcnt[node].range(pl, pr), fsum[node].range(pl, pr));
    };

    for (auto& q : qs) {
        if (A[q.c] != q.x) {
            activate(q.c, A[q.c], -1);
            activate(q.c, q.x, +1);
            A[q.c] = q.x;
        }
        int l = q.l, r = q.r;
        ll k = q.k;

        auto total = queryRange(1, l, r);
        if (total.second < k) {
            cout << -1 << '\n';
            continue;
        }

        ll eatCnt = 0;
        int node = 1;
        while (node < SZ) {
            int right = 2 * node + 1;                  // 右儿子对应更大的美味度
            auto [cntR, sumR] = queryRange(right, l, r);
            if (sumR >= k) {
                node = right;                          // 右儿子内部就能凑够 k
            } else {
                eatCnt += cntR;                        // 右儿子全部吃掉
                k -= sumR;
                node = 2 * node;                       // 去左儿子继续
            }
        }
        int vid = node - SZ;
        ll v = valOf[vid];
        auto [cntL, sumL] = queryRange(node, l, r);
        ll take = (k + v - 1) / v;                     // 该值只需吃 ceil(k/v) 个
        if (take > cntL) take = cntL;
        eatCnt += take;
        cout << eatCnt << '\n';
    }
    return 0;
}

复杂度分析

时间复杂度：建树 $O\bigl((N+Q)\log(N+Q)\bigr)$ ；每次修改与每次查询均为 $O(\log^2(N+Q))$ ，总 $O\bigl((N+Q)\log^2(N+Q)\bigr)$
空间复杂度： $O\bigl((N+Q)\log(N+Q)\bigr)$ （值树每层存储全部 $(N+Q)$ 个可能的二元组，共 $\log$ 层）