AtCoder Beginner Contest 426 题解

项目	内容
比赛时间	2025-10-04
比赛链接	https://atcoder.jp/contests/abc426
题目数量	A–G 共 7 题

比赛概览

本场 A–C 延续了 ABC 一贯的入门节奏：A 是简单的版本字符串比较，B 是计数题，C 考察一个"最老版本指针单调推进"的关键观察，从而把看似暴力的过程压到 $O(N+Q)$。D 是一道非常巧妙的组合计数题，核心在于"从未被操作过的字符在原串中必须连成一段"，进而转化为求最长连续相同字符段。E 是几何题，把两个人的相对运动拆成两条线段，把最小距离归结为"点到线段的最短距离"。F 与 G 是本场最有区分度的两道题：F 需要用懒标记线段树维护"售罄事件"（每个商品至多售罄一次，故总复杂度带一个 $\log$ 也可接受），G 需要用基于序列的分治配合 0/1 背包 DP 回答区间背包查询。建议重点掌握 D、F、G 三题的处理手法。

---

A - OS Versions

题目链接：https://atcoder.jp/contests/abc426/tasks/abc426_a

题目大意

某操作系统的版本按时间先后为 Ocelot、Serval、Lynx。给定版本 $X$ 与版本 $Y$，判断 $X$ 是否与 $Y$ 相同或比 $Y$ 更新。输入一行两个字符串，输出 Yes 或 No。

思路

• 关键观察：版本之间的先后关系只有三种，直接按时间顺序给每个版本编号即可把字符串比较转化为整数比较。例如令

  $$\text{Ocelot}=1,\quad \text{Serval}=2,\quad \text{Lynx}=3,$$

  则 $X$ 不早于 $Y$ 等价于编号满足 $mp[X] \ge mp[Y]$。
• 也可以直接枚举 $9$ 种情况：其中答案为 No 的只有 $X$ 严格旧于 $Y$ 的 $3$ 种组合，即 $(\text{Ocelot},\text{Serval})$、$(\text{Ocelot},\text{Lynx})$、$(\text{Serval},\text{Lynx})$，其余情况（包括 $X=Y$）都输出 Yes。
• 需要注意相等时（如 Ocelot Ocelot）答案也是 Yes，不要漏掉。

参考代码

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

int main() {
    map<string, int> ver = {
        {"Ocelot", 1},
        {"Serval", 2},
        {"Lynx", 3}
    };
    string x, y;
    cin >> x >> y;
    cout << (ver[x] >= ver[y] ? "Yes" : "No") << '\n';
    return 0;
}

复杂度分析

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

---

B - The Odd One Out

题目链接：https://atcoder.jp/contests/abc426/tasks/abc426_b

题目大意

给定一个长度至少为 $3$ 的小写字母字符串 $S$。$S$ 中恰好包含两种字符，且恰好有一个字符与其他字符不同（即它出现一次）。输出这个"与众不同"的字符。

思路

• 方法一（计数）：统计每种字符出现的次数，输出出现次数恰好为 $1$ 的字符即可。由于 $|S| \le 10$，用 map 或长度 $26$ 的数组都很容易。题目保证恰有一个字符出现一次，因此答案唯一。
• 方法二（排序，利用结构）：把 $S$ 排序得到 $S'$。因为只有两种字符且一种只出现一次，排序后这个唯一的字符必然出现在两端：
  • 若 $S'[0] \ne S'[1]$，说明 $S'$ 的第一个字符就是只出现一次的那个；
  • 否则前两个相同，答案就是最后一个字符 $S'[|S|-1]$。
    这个方法无需统计频次，代码更短。
• 边界情况：长度至少为 $3$，所以 $S'$ 至少有 $3$ 个字符，S'.back() 一定存在。

参考代码

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

int main() {
    string s;
    cin >> s;
    map<char, int> cnt;
    for (char c : s) cnt[c]++;
    for (auto [c, k] : cnt) {
        if (k == 1) {
            cout << c << '\n';
            return 0;
        }
    }
    return 0;
}

复杂度分析

• 时间复杂度：$O(|S|\log|S|)$（用数组则为 $O(|S|+\sigma)$，$\sigma=26$）。
• 空间复杂度：$O(\sigma)$。

---

C - Upgrade Required

题目链接：https://atcoder.jp/contests/abc426/tasks/abc426_c

题目大意

有 $N$ 个版本（编号 $1,2,\dots,N$，数字越小越旧）和 $N$ 台电脑，初始时第 $i$ 台电脑的版本为 $i$。依次进行 $Q$ 次操作，第 $i$ 次操作为：把所有当前版本不超过 $X_i$ 的电脑升级到版本 $Y_i$（保证 $X_i < Y_i$），并输出本次被升级的电脑数量。

思路

• 关键观察：当前存在的版本集合始终是一段连续区间。设 $O$ 为当前所有电脑中的最旧版本，则任意时刻，各电脑的版本集合恰好是 $\{O, O+1, \dots, N\}$。
  • 用归纳法证明：初始版本集合为 $\{1,2,\dots,N\}$，$O=1$。假设某次操作前版本集合为 $\{O,\dots,N\}$。考虑操作 $(X,Y)$：
    • 若 $X < O$，则没有任何电脑的版本 $\le X$，版本集合不变；
    • 否则，版本在 $[O, X]$ 内的电脑（恰好是版本集合的一个连续前缀）全部升到 $Y$。由于 $X < Y \le N$，升级后这些电脑的版本都是 $Y$，而版本 $> X$ 的电脑保持不动，新的版本集合为 $\{Y\} \cup \{X+1,\dots,N\} = \{X+1,\dots,N\}$，即新的最旧版本为 $O' = X+1$。
• 算法：维护当前最旧版本 $O$ 与计数数组 $cnt[v]$（当前版本恰为 $v$ 的电脑数）。对每次操作 $(X,Y)$：
  1. 若 $X < O$，本次没有电脑被升级，输出 $0$；
  2. 否则令 $res = 0$，反复执行 while (O <= X)：把版本 $O$ 的所有电脑（数量 $cnt[O]$）计入 $res$，并转移到版本 $Y$，即 $cnt[Y] \mathrel{+}= cnt[O]$，然后 $O \gets O+1$；最后输出 $res$。
• 为什么正确：由于版本集合是连续区间，本次升级的电脑数量恰好是 $\sum_{v=O}^{X} cnt[v]$，上述循环精确累加了这一数量并把它们迁移到 $Y$。
• 为什么高效：指针 $O$ 从 $1$ 开始只增不减，最多增加到 $N$，因此所有操作中内层循环的总执行次数不超过 $N$，总复杂度为 $O(N+Q)$。这是本问题的关键——不能对每个操作重新扫描区间。
• 易错点：$cnt[O..X]$ 中的旧值在转移后不必清零，因为 $O$ 已经越过这些位置、今后不会再访问；同时 $Y > X \ge O$ 保证 $Y$ 落在仍然"活跃"的版本区间内，$cnt[Y]$ 不会被清掉。

参考代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<long long> cnt(n + 2, 0);
    for (int i = 1; i <= n; ++i) cnt[i] = 1;
    int o = 1; // 当前最旧版本
    while (q--) {
        int x, y;
        cin >> x >> y;
        long long res = 0;
        while (o <= x) {
            res += cnt[o];
            cnt[y] += cnt[o];
            ++o;
        }
        cout << res << '\n';
    }
    return 0;
}

复杂度分析

• 时间复杂度：$O(N+Q)$。
• 空间复杂度：$O(N)$。

---

D - Pop and Insert

题目链接：https://atcoder.jp/contests/abc426/tasks/abc426_d

题目大意

给定长度为 $N$ 的 01 字符串 $S$。一次操作：删除第一个或最后一个字符，翻转（0 变 1、1 变 0），再把它插回任意位置。求使 $S$ 中所有字符相同所需的最少操作次数。共 $T$ 组测试，所有 $N$ 之和不超过 $5\times 10^5$。

思路

先考虑把最终所有字符都变成 0 的情况（变成 1 完全对称）。

• 下界分析：
  • 原串中每个 1 都要被翻转奇数次才能变成 0，因此每个 1 至少被操作 $1$ 次。
  • 原串中每个 0 要翻转偶数次才能保持为 0，因此它要么不操作，要么至少操作 $2$ 次。
  • 关键观察：若初始位于第 $i$ 位和第 $j$ 位（$i<j$）的字符从未被操作，则它们之间任何字符都无法被操作。因为一个字符要被操作，必须先把它左边（从前面弹出）或右边（从后面弹出）的所有字符全部弹出；而第 $i$ 位（或第 $j$ 位）的字符从未被弹出，会永远挡在中间。因此从未被操作的字符在原串中必须构成一段连续区间。
  • 从未被操作的字符都必须是 0，所以它们只能取某一段连续的 0，长度至多为最长连续 0 段的长度 $M_0$。
  • 设 $C_0$ 为 0 的个数、$C_1$ 为 1 的个数（$C_0+C_1=N$）。则除最长 0 段之外的 $C_0-M_0$ 个 0 各自至少操作 $2$ 次，所有 $C_1$ 个 1 各自至少操作 $1$ 次，故下界为

    $$2(C_0 - M_0) + C_1.$$

• 上界（构造，说明下界可达到）：把最长的一段连续 0（记为保护块 $B$）保护起来，永不操作它。
  1. 处理 $B$ 左侧：反复弹出当前串的第一个字符并翻转——由于弹出后插回，操作过的字符不会挡路，每次弹出时串首必然仍是 $B$ 左侧未处理的字符。若翻转后是 0（原本是 1），插回串首即完成；若翻转后是 1（原本是 0），插到串尾，等待第二次翻转。于是 $B$ 左侧每个字符恰好被操作 $1$ 次。
  2. 处理串尾：此时串尾的字符要么是第 1 步从左侧插过来的 1，要么是 $B$ 右侧尚未处理的字符。反复弹出串尾字符并翻转：若翻转为 0，插回串首（完成）；若翻转为 1（即 $B$ 右侧原本为 0 的字符第一次被翻转），插回串尾，使其紧接着被再次弹出、完成第二次翻转。
  3. 最终所有字符都变成 0。统计操作次数：$B$ 之外的每个字符都至少被弹出 $1$ 次，共 $N - M_0$ 次；其中原本为 0 的（$C_0-M_0$ 个）额外多弹出 $1$ 次。总数为

     $$(N - M_0) + (C_0 - M_0) = 2(C_0 - M_0) + C_1,$$

     正好等于下界。
• 因此目标为全 0 的答案是 $2(C_0-M_0)+C_1$。对称地，目标为全 1 的答案是 $2(C_1-M_1)+C_0$（$M_1$ 为最长连续 1 段的长度）。最终答案取两者较小者：

  $$\text{ans} = \min\Big(2(C_0-M_0)+C_1,\; 2(C_1-M_1)+C_0\Big).$$

• 实现：一次扫描统计 0、1 的个数与各自的最长连续段长度即可，注意段长度的统计要按字符分段扫。

参考代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n;
        string s;
        cin >> n >> s;
        vector<int> cnt(2, 0), mx(2, 0);
        for (int i = 0; i < n; ) {
            int j = i;
            while (j < n && s[j] == s[i]) ++j;
            int c = s[i] - '0';
            cnt[c] += j - i;
            mx[c] = max(mx[c], j - i);
            i = j;
        }
        int ans = 2 * n;
        for (int c = 0; c < 2; ++c) {
            ans = min(ans, 2 * (cnt[c] - mx[c]) + cnt[1 - c]);
        }
        cout << ans << '\n';
    }
    return 0;
}

复杂度分析

• 时间复杂度：每组 $O(N)$，总计 $O(\sum N)$。
• 空间复杂度：$O(1)$。

---

E - Closest Moment

题目链接：https://atcoder.jp/contests/abc426/tasks/abc426_e

题目大意

高桥从 $(TS_X,TS_Y)$ 走向 $(TG_X,TG_Y)$，青木从 $(AS_X,AS_Y)$ 走向 $(AG_X,AG_Y)$。两人同时出发，速度均为 $1$，到达各自终点后停下（停下的时刻可以不同）。求两人距离的最小值，包含出发时刻和双方都停下之后的时刻。共 $T$ 组测试。

思路

• 问题转化：设 $A$、$B$ 为高桥的起点与终点，$C$、$D$ 为青木的起点与终点；令 $p = |AB|$、$q = |CD|$ 分别为两人的行走时长。两人对称，不妨设 $p \ge q$（否则交换两人的角色）。
• 只需要考虑 $t \in [0, p]$：$p$ 时刻之后两人都已停下，距离恒定。
• 把时间分成两段：设 $E$ 为时刻 $q$（青木到达终点）时高桥所在的位置。则：
  • 阶段 1，$t \in [0, q]$：高桥从 $A$ 走向 $E$，青木从 $C$ 走向 $D$，两人同时出发、同时到达。
  • 阶段 2，$t \in [q, p]$：高桥从 $E$ 走向 $B$，青木停在 $D$。
• 相对运动是分段线性的：记相对位置 $R(t) = $ 高桥位置 $-$ 青木位置。在阶段 1 中，两人的位置都是关于 $t$ 的线性函数，故 $R(t)$ 也从 $R(0)=A-C$ 线性变化到 $R(q)=E-D$，即 $\{R(t): t\in[0,q]\}$ 恰好是连接 $A-C$ 与 $E-D$ 两点的整条线段。在阶段 2 中，$R(t)$ 从 $E-D$ 线性变化到 $B-D$，即另一条线段。
• 最小距离 $=$ 点到线段的最短距离：两人的距离为 $|R(t)|$，因此答案就是两条线段分别到原点的最短距离中的较小者。
• 点到线段距离的计算：设线段端点 $P,Q$，其上点 $X(\lambda)=P+\lambda(Q-P)$，$\lambda \in [0,1]$。最小化

  $$f(\lambda) = |X(\lambda)|^2 = |P|^2 + 2\lambda\, P\cdot(Q-P) + \lambda^2 |Q-P|^2.$$

  这是关于 $\lambda$ 的凸二次函数，无约束最优点为 $\lambda^* = -\dfrac{P\cdot(Q-P)}{|Q-P|^2}$，把它截断到 $[0,1]$ 后代入即可（当 $|Q-P|=0$ 时线段退化为点，直接取 $|P|$）。这给出精确的 $O(1)$ 做法；官方题解使用三分法（约 $60$ 次迭代）也可以，精度同样足够。
• 精度：坐标绝对值 $\le 100$，用 double 即可，按题目要求输出 15 位小数。

参考代码

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

struct Pt { double x, y; };

// 原点 (0,0) 到线段 PQ 的最短距离
double dist_seg_to_origin(Pt p, Pt q) {
    Pt v = {q.x - p.x, q.y - p.y};
    double len2 = v.x * v.x + v.y * v.y;
    double t = 0;
    if (len2 > 0) t = -(p.x * v.x + p.y * v.y) / len2;
    t = max(0.0, min(1.0, t));
    double x = p.x + t * v.x;
    double y = p.y + t * v.y;
    return sqrt(x * x + y * y);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    cout << fixed << setprecision(15);
    while (T--) {
        Pt a, b, c, d;
        cin >> a.x >> a.y >> b.x >> b.y;
        cin >> c.x >> c.y >> d.x >> d.y;
        double p = hypot(b.x - a.x, b.y - a.y); // 高桥行走时间
        double q = hypot(d.x - c.x, d.y - c.y); // 青木行走时间
        if (p < q) { // 保证 p >= q
            swap(a, c);
            swap(b, d);
            swap(p, q);
        }
        // E：时刻 q 时高桥的位置
        Pt e = {a.x + (b.x - a.x) * q / p,
                a.y + (b.y - a.y) * q / p};
        // 阶段 1：相对位置从 (a-c) 到 (e-d)；阶段 2：从 (e-d) 到 (b-d)
        Pt r1 = {e.x - d.x, e.y - d.y};
        double ans = dist_seg_to_origin({a.x - c.x, a.y - c.y}, r1);
        ans = min(ans, dist_seg_to_origin(r1, {b.x - d.x, b.y - d.y}));
        cout << ans << '\n';
    }
    return 0;
}

复杂度分析

• 时间复杂度：每组 $O(1)$，总计 $O(T)$。
• 空间复杂度：$O(1)$。

---

F - Clearance

题目链接：https://atcoder.jp/contests/abc426/tasks/abc426_f

题目大意

商店有 $N$ 种商品，第 $i$ 种商品的库存为 $A_i$。依次处理 $Q$ 笔订单，第 $i$ 笔订单为：购买商品 $l_i,l_i+1,\dots,r_i$ 各 $k_i$ 件，若某商品库存不足 $k_i$ 件，则买走其全部剩余库存。输出每笔订单实际买到商品的总件数。库存只会减少。

思路

• 每个商品的三种状态：库存充足、本单内售罄（剩余不足 $k$）、已售罄（剩余 $0$，之后不再参与）。关键是"售罄事件"：某商品在某笔订单中被买空，此后它永远不会再被真正购买（即便出现在后续订单里，也只能买 $0$ 件）。
• 算法：对订单 $(l, r, k)$：
  1. 先假设区间 $[l, r]$ 内每个"还没售罄"的商品都能买 $k$ 件，得初值

     $$res = (\text{区间内未售罄商品数}) \times k.$$

  2. 把 $[l, r]$ 内所有库存都减去 $k$（区间减）。
  3. 区间内可能有些商品库存变成负数，它们在本单售罄了。设某商品当前库存为 $-s$（即它原本只剩 $s < k$ 件），实际只买走 $s$ 件，而我们按 $k$ 件计了数，故应从答案中修正 $res \mathrel{+}= (-s)$（即 $res$ 减去 $k-s$）。修正后把这个商品的库存设为一个极大的数 $big$，并把它从"未售罄商品数"中删除，保证它今后不会再触发售罄事件。
  4. 步骤 3 可能要反复执行（一个订单中可能有多个商品同时售罄），直到区间内最小库存 $\ge 0$。
• 数据结构：
  • 用懒标记线段树维护区间加与区间最小值，并支持单点赋值；用另一个求和结构（线段树或树状数组）维护每个位置是否还"未售罄"（初始全为 $1$，售罄后置 $0$），用于计算"区间内未售罄商品数"。
  • 找到区间内负值位置：需要"寻找 $[l, r)$ 内最左的负库存"。用线段树自带的 max_right（或自定义一个"找第一个负值"的递归函数）实现：谓词 $g(x) = (x \ge 0)$ 具有单调性——一旦某个前缀的最小值 $< 0$，再向右扩展只会让最小值更小，仍然 $< 0$，因此"首个使前缀最小值变负的位置"可以二分定位。
• 复杂度论证：每个商品售罄一次后就被置为 $big$；而所有订单累计减去的总量不超过 $Q \cdot \max k = 3\times 10^5 \times 10^9 = 3\times 10^{14} \ll big = 4\times 10^{18}$，故每个商品至多售罄一次，整个过程中 while 循环的迭代总数不超过 $N$。因此总复杂度为 $O((N+Q)\log N)$。
• 数值范围：$A_i \le 10^{15}$，答案与中间量都要用 long long。

参考代码

以下实现不依赖 AtCoder Library，使用自写的懒标记线段树（区间加、区间最小值、单点赋值、查询区间内第一个负值）与树状数组（单点减 1、区间和）。

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

const ll BIG = (ll)4e18;

// 区间加、区间最小值、单点赋值、查询 [ql, n) 内第一个负值位置
struct SegTree {
    int n;
    vector<ll> mn, lazy;
    SegTree(const vector<ll>& a) {
        int sz = (int)a.size();
        n = 1;
        while (n < sz) n <<= 1;
        mn.assign(2 * n, BIG);
        lazy.assign(2 * n, 0);
        for (int i = 0; i < sz; ++i) mn[n + i] = a[i];
        for (int i = n - 1; i >= 1; --i) mn[i] = min(mn[i << 1], mn[i << 1 | 1]);
    }
    void apply(int v, ll x) { mn[v] += x; lazy[v] += x; }
    void push(int v) {
        if (lazy[v]) {
            apply(v << 1, lazy[v]);
            apply(v << 1 | 1, lazy[v]);
            lazy[v] = 0;
        }
    }
    void add(int v, int nl, int nr, int ql, int qr, ll x) {
        if (qr <= nl || nr <= ql) return;
        if (ql <= nl && nr <= qr) { apply(v, x); return; }
        push(v);
        int mid = (nl + nr) >> 1;
        add(v << 1, nl, mid, ql, qr, x);
        add(v << 1 | 1, mid, nr, ql, qr, x);
        mn[v] = min(mn[v << 1], mn[v << 1 | 1]);
    }
    ll prod(int v, int nl, int nr, int ql, int qr) {
        if (qr <= nl || nr <= ql) return BIG;
        if (ql <= nl && nr <= qr) return mn[v];
        push(v);
        int mid = (nl + nr) >> 1;
        return min(prod(v << 1, nl, mid, ql, qr),
                   prod(v << 1 | 1, mid, nr, ql, qr));
    }
    void setval(int v, int nl, int nr, int idx, ll x) {
        if (nr - nl == 1) { mn[v] = x; lazy[v] = 0; return; }
        push(v);
        int mid = (nl + nr) >> 1;
        if (idx < mid) setval(v << 1, nl, mid, idx, x);
        else setval(v << 1 | 1, mid, nr, idx, x);
        mn[v] = min(mn[v << 1], mn[v << 1 | 1]);
    }
    // 返回 [ql, n) 中最左边的负值位置，保证存在
    int first_negative(int v, int nl, int nr, int ql) {
        if (nr <= ql || mn[v] >= 0) return -1;
        if (nr - nl == 1) return nl;
        push(v);
        int mid = (nl + nr) >> 1;
        int r = first_negative(v << 1, nl, mid, ql);
        if (r != -1) return r;
        return first_negative(v << 1 | 1, mid, nr, ql);
    }
};

// 树状数组：单点加、区间和
struct BIT {
    int n;
    vector<ll> bit;
    BIT(int n_) : n(n_), bit(n_ + 1, 0) {}
    void add(int i, ll x) { for (++i; i <= n; i += i & -i) bit[i] += x; }
    ll sum(int i) { ll r = 0; for (; i > 0; i -= i & -i) r += bit[i]; return r; } // [0, i)
    ll range(int l, int r) { return sum(r) - sum(l); }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<ll> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    SegTree seg(a);
    BIT bit(n);
    for (int i = 0; i < n; ++i) bit.add(i, 1); // 初始全部未售罄
    int q;
    cin >> q;
    while (q--) {
        int l, r;
        ll k;
        cin >> l >> r >> k;
        --l; // 转为 0 下标左闭右开 [l, r)
        ll res = bit.range(l, r) * k;
        seg.add(1, 0, seg.n, l, r, -k);
        while (seg.prod(1, 0, seg.n, l, r) < 0) {
            int pos = seg.first_negative(1, 0, seg.n, l);
            res += seg.prod(1, 0, seg.n, pos, pos + 1); // 修正：实际只买了剩余的 s 件
            seg.setval(1, 0, seg.n, pos, BIG);          // 售罄后置为极大值
            bit.add(pos, -1);                           // 不再计入"未售罄"
        }
        cout << res << '\n';
    }
    return 0;
}

复杂度分析

• 时间复杂度：$O((N+Q)\log N)$。
• 空间复杂度：$O(N)$。

---

G - Range Knapsack Query

题目链接：https://atcoder.jp/contests/abc426/tasks/abc426_g

题目大意

有 $N$ 件物品，第 $i$ 件的重量为 $W_i$、价值为 $V_i$。有 $Q$ 个查询，第 $j$ 个查询给出 $L_j, R_j, C_j$：从物品 $L_j,L_j+1,\dots,R_j$ 中选若干件（可以一件不选），使总重量不超过 $C_j$，求能得到的最大总价值。其中 $W_i \le 500$，$C_j \le 500$。

思路

• 为什么不能对每个查询单独做背包：单个查询的 0/1 背包复杂度 $O((R-L)\cdot C)$，$Q$ 个查询会到 $O(QNC)$，不可行。
• 序列分治（CDQ 式）：定义递归函数 $f(l,r)$ 处理"查询区间完全落在 $[l,r)$ 内"的所有查询。取 $m = \lfloor (l+r)/2 \rfloor$：
  • 查询区间完全在左半边 $[l,m)$ 内 $\Rightarrow$ 递归进 $f(l,m)$；
  • 完全在右半边 $[m,r)$ 内 $\Rightarrow$ 递归进 $f(m,r)$；
  • 跨过 $m$ 的查询（$l \le L < m \le R < r$）在本层直接回答。
• 跨 $m$ 查询的回答：预处理两类 DP：
  • $dp_l[i][j]$（$l \le i < m$）：从物品 $[i, m)$ 中选、总重量不超过 $j$ 的最大价值；
  • $dp_r[i][j]$（$m \le i \le r$）：从物品 $[m, i)$ 中选、总重量不超过 $j$ 的最大价值。
  • 从空背包 $dp[m]$（全 $0$）出发递推：$dp_l[i] = dp_l[i+1]$ 再放入物品 $i$（$i$ 从 $m-1$ 递减到 $l$）；$dp_r[i] = dp_r[i-1]$ 再放入物品 $(i-1)$（$i$ 从 $m+1$ 递增到 $r$）。放物品即标准 0/1 背包转移

    $$dp'[j] = \max\big(dp[j],\; dp[j-W_i] + V_i\big).$$

  • 对跨 $m$ 的查询 $(L,R,C)$，左右两部分物品不相交，选择可以按重量切分：任何合法方案在左侧用掉重量 $j_L$、右侧用掉重量 $j_R \le C - j_L$，故答案为

    $$\max_{0 \le j \le C}\Big(dp_l[L][j] + dp_r[R][C-j]\Big).$$

    这是因为"不超过容量"型的背包 DP 关于容量是单调的，右侧取容量 $C-j$ 一定不差于取 $j_R \le C-j$；反之任取一个 $j$，左右两部分各自的最优选择互不影响、可以同时取，构成合法方案。这就是背包可拼接的性质。
• 正确性：每个查询要么在某层作为"跨 $m$"查询被回答，要么最终落到长度恰为 $1$ 的区间（单物品）在递归边界直接判断 $C \ge W_i$ 是否取它。
• 复杂度：每个递归节点中，DP 填充对区间内每个物品做一次 $O(K)$ 转移，一层所有节点合计 $O(NK)$，层数 $O(\log N)$；每个查询只在一层被回答一次，代价 $O(K)$。其中 $K$ 为容量上限 $+1$（$K=501$）。总复杂度

  $$O\big(K(Q + N\log N)\big).$$

• 实现细节：DP 表大小为 $(N+1)\times K$ 的 long long（容量 $C \le 500$，取 $K=510$ 留余量）；递归时传"属于本节点的查询下标列表"，避免每次扫描全部查询。

参考代码

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

using ll = long long;
const int K = 510;

struct Query { int l, r, c; };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> w(n), v(n);
    for (int i = 0; i < n; ++i) cin >> w[i] >> v[i];
    int q;
    cin >> q;
    vector<Query> query(q);
    for (int i = 0; i < q; ++i) {
        cin >> query[i].l >> query[i].r >> query[i].c;
        --query[i].l; // 转为 0 下标左闭右开 [l, r)
    }
    vector<ll> ans(q, 0);
    vector<vector<ll>> dp(n + 1, vector<ll>(K, 0));

    // 把物品 i 加入背包：pre -> nx
    auto upd = [&](const vector<ll>& pre, vector<ll>& nx, int i) {
        for (int j = 0; j < K; ++j) {
            nx[j] = pre[j];
            if (j >= w[i]) nx[j] = max(nx[j], pre[j - w[i]] + v[i]);
        }
    };

    function<void(int, int, const vector<int>&)> f =
        [&](int l, int r, const vector<int>& qid) {
            if (l + 1 == r) { // 区间只含物品 l
                for (int id : qid)
                    if (query[id].c >= w[l]) ans[id] = v[l];
                return;
            }
            int m = (l + r) >> 1;
            fill(dp[m].begin(), dp[m].end(), 0); // 空背包
            for (int i = m - 1; i >= l; --i) upd(dp[i + 1], dp[i], i);     // dp[i]: 物品 [i, m)
            for (int i = m + 1; i <= r; ++i) upd(dp[i - 1], dp[i], i - 1); // dp[i]: 物品 [m, i)
            vector<int> ql, qr;
            for (int id : qid) {
                int L = query[id].l, R = query[id].r, C = query[id].c;
                if (R <= m) {
                    ql.push_back(id);
                } else if (L >= m) {
                    qr.push_back(id);
                } else {
                    // 跨 m 的查询：左侧 [L, m) 与右侧 [m, R) 拼接
                    for (int j = 0; j <= C; ++j)
                        ans[id] = max(ans[id], dp[L][j] + dp[R][C - j]);
                }
            }
            f(l, m, ql);
            f(m, r, qr);
        };

    vector<int> qid(q);
    iota(qid.begin(), qid.end(), 0);
    f(0, n, qid);
    for (int i = 0; i < q; ++i) cout << ans[i] << '\n';
    return 0;
}

复杂度分析

• 时间复杂度：$O(K(Q + N\log N))$，其中 $K = 501$。
• 空间复杂度：$O(NK)$。