阅读这份题解，讲解这道题，脱离原题解，你讲解使用的不同种类符号数量尽可能少，为了代码可读性允许在正确...

这道题的关键是：把“选哪些题回答”变成“选一个分界点”，再利用分界点的单调性减少枚举。

下面先推导这个过程，再给出不使用主席树、只使用普通线段树的完整实现。

一、先确定对手会怎么改答案

每道题答对得到 $a$，答错得到 $-b$，不回答得到 $0$。

对于一次询问，我们必须回答至少 $k$ 道题，对手可以修改其中至多 $k$ 道，让我们尽可能少得分。注意“至少回答 $k$ 道”这个要求，因此答案可能是负数，不能简单地选择全部不答。题目中题数最多为 $2\times 10^5$。(USACO)

一道题被改以后，得分从 $a$ 变成 $-b$，所以我们会少得

$$a+b$$

分。

因此，无论我们回答了哪些题，对手都会修改其中 $a+b$ 最大的 $k$ 道。(USACO)

于是，先把所有题按照 $a+b$ 从大到小排序。之后提到的位置，都是排序后的位置。

这样，对于我们选出来的题：

前 $k$ 道被改，每道贡献 $-b$；剩下的不会被改，每道贡献 $a$。

$a+b$ 相同的题可以任意排序，因为改它们造成的减分相同。

二、为什么只需要枚举一个分界点？

先考虑 $k>0$。

假设我们已经选好了一些题，把最后一道被改的题的位置记作 $x$。

那么，位置 $x$ 后面的题，即使我们全部回答，也不会影响前面那 $k$ 道被改的题。它们都能得到正的 $a$ 分。

所以：

最后一道被改的题之后，所有题都应该回答。

选题方案因此可以整理成：

• 前 $x$ 道题里，选择恰好 $k$ 道，它们全部被改。
• 后面的题全部回答，它们全部答对。

前面选出的题只贡献 $-b$，所以当然选 $b$ 最小的 $k$ 道。

于是，分界点固定之后，最优得分就是：

$$\boxed{ \text{得分} = x\text{ 后面所有 }a\text{ 的和} - \text{前 }x\text{ 道题中最小的 }k\text{ 个 }b\text{ 的和} }$$

枚举所有满足 $k\le x\le n$ 的分界点，取最大值即可。这个表达式也是题解中枚举分界点做法的核心。(Luogu)

这里有一个容易疑惑的细节

按照“前面选最小的 $k$ 个 $b$”的规则，第 $x$ 道题不一定被选中。

这没有关系。现在的 $x$ 只是划分前后两段的位置，不再要求它恰好是最后一道被改的题。

这样做依然正确：

不会产生非法方案。 前面恰好回答 $k$ 道，后面全部回答。按照排序顺序，对手可以选择修改前面这 $k$ 道，而且这是最坏情况。

不会漏掉最优方案。 任意最优方案都可以补上最后一道被改的题之后的所有题；再把前面选出的题替换成 $b$ 最小的 $k$ 道，得分只会变好。

对于 $k=0$，允许 $x=0$，就表示所有题都回答、没有题被改。

举个例子

假设排序后是：

位置	答对得分 $a$	答错扣分 $b$	$a+b$
1	8	9	17
2	1	10	11
3	5	2	7
4	3	1	4

考虑 $k=1$。

选择 $x=3$ 时，前三道题里只回答 $b$ 最小的第三题，最后一道题也回答。

第三题被改，得到 $-2$；第四题没被改，得到 $3$。最终得分为 $1$。

四个分界点的得分依次为：

$$0,\ -1,\ 1,\ -1$$

所以最优分界点是 $3$。

到这里，原来的选题问题已经变成了：

对每个 $k$，找一个最好的 $x$。

三、为什么 $k$ 越大，最优分界点不会向左移动？

这是整道题最重要的性质。

我们约定：如果多个分界点得分相同，选择最靠左的那个。

在这个约定下，随着 $k$ 增大，最优分界点只会保持不变或者向右移动。官方分析也使用了这一决策单调性。(USACO)

不需要复杂的交换论证，直接观察“多改一道题会多扣多少分”。

1. 固定分界点，多改一道会发生什么？

分界点固定时，后面所有 $a$ 的和不变。

前面原本选择最小的 $k$ 个 $b$，现在需要选择最小的 $k+1$ 个 $b$。

因此，得分会减少：

这个前缀中，第 $k+1$ 小的 $b$。

2. 分界点越靠右，这次额外扣分不会越大

比较一个靠左的分界点和一个靠右的分界点。

靠右的前缀包含靠左前缀中的所有题，还多了一些题。

候选题变多以后，第 $k+1$ 小的 $b$ 只可能变小或不变，不可能变大。

所以：

当 $k$ 增加一时，靠右的分界点，得分减少得不会比靠左的更多。

3. 原来落后的左侧分界点，不可能反超

考虑当前 $k$ 的最优分界点。

因为同分时选择最靠左的，所以在它左侧的所有合法分界点，得分都严格更低。

当 $k$ 增加一：

• 左侧分界点原本就落后；
• 它们这次减少的得分，又不比当前分界点少。

因此，它们仍然落后，不可能成为新的最优分界点。

有一个边界情况：当前分界点是 $x=k$，增加一次修改后，它不再合法。但这时新的分界点至少是 $k+1$，自然也只能在它右侧。

单调性得证。

四、利用单调性分治，而不是逐个询问完整枚举

假设现在要处理一段连续的 $k$，并且已经知道：这些 $k$ 的最优分界点，都在某个候选区间里。

取中间的 $k$，枚举它的候选分界点，找到最优位置。

根据单调性：

更小的 $k$，最优分界点不会超过这个位置。
更大的 $k$，最优分界点不会小于这个位置。

于是可以把问题分成左右两部分，继续递归。

代码中用：

cpp
solve(firstK, lastK, firstCut, lastCut)

表示：

计算 firstK 到 lastK 的答案；它们的最优分界点都在 firstCut 到 lastCut 之间。

初始调用：

cpp
solve(0, n, 0, n);

这里直接预处理所有 $k$ 的答案，之后按输入顺序输出即可。这样不需要对询问排序，也不需要记录询问原来的编号。

注意，单调的是“最优分界点”，不是“得分随分界点单调变化”。

前面例子的得分是 $0,-1,1,-1$，所以不能从左往右走，看到得分下降就停下来，也不能直接三分。

五、不用主席树，普通线段树就够了

现在只剩一个需要高效计算的部分：

前 $x$ 道题中，最小的 $k$ 个 $b$ 的和。

普通线段树配合分界点的增删，也可以完成这个任务，不必保存所有前缀的历史版本。(USACO)

1. 线段树按 $b$ 的大小排列

先把题按 $b$ 从小到大编号。

线段树的叶子按照这个编号排列。因此，左边的叶子对应较小的 $b$，右边对应较大的 $b$。

线段树中的顺序是 $b$ 的大小顺序，不是前面按照 $a+b$ 排出的题目顺序。

每个节点保存两个信息：

cpp
count  // 这个范围内，目前有多少道题
sum    // 这些题的 b 的总和

当前分界点为 $x$ 时，线段树只放入前 $x$ 道题。

2. 怎么查询最小的 $k$ 个数之和？

看左子树里有多少个数。

如果左子树已经有至少 $k$ 个数，那么答案全部在左子树里，继续向左查询。

否则，左子树里的数全部取走，再去右子树补足剩下的数量。

每次只继续进入一棵子树，因此一次查询是 $O(\log n)$。

3. 怎么切换前缀？

维护当前已经放入了前多少道题。

要把分界点向右移动，就加入新经过的题；向左移动，就删除退出前缀的题。

cpp
movePrefix(x);

执行之后，线段树就恰好保存前 $x$ 道题。

为避免递归之间互相干扰，我们统一约定：

每次 solve 调用前和返回后，线段树都保存前 firstCut 道题。

代码里明确恢复状态，虽然会多做一些增删，但逻辑清楚，而且不改变最终的复杂度。

六、完整代码：C++17

cpp
#include <algorithm>
#include <iostream>
#include <limits>
#include <vector>
using namespace std;

struct Question {
    long long a, b;
    int rank;  // 按 b 从小到大排列时的编号
};

struct Node {
    int count = 0;
    long long sum = 0;
};

int n;

vector<Question> question;
vector<long long> value;
vector<long long> suffix;
vector<long long> answer;
vector<Node> tree;

int currentPrefix = 0;

// 加入或删除一道题。
// delta 为 1 表示加入，为 -1 表示删除。
void change(int node, int left, int right, int rank, int delta) {
    tree[node].count += delta;
    tree[node].sum += value[rank] * delta;

    if (left == right) return;

    int middle = (left + right) / 2;

    if (rank <= middle) {
        change(node * 2, left, middle, rank, delta);
    } else {
        change(node * 2 + 1, middle + 1, right, rank, delta);
    }
}

// 查询当前线段树中，最小的 k 个 b 的和。
long long smallestSum(int node, int left, int right, int k) {
    if (k == 0) return 0;

    // 整个节点里的数都要选，直接返回总和。
    if (k == tree[node].count) {
        return tree[node].sum;
    }

    if (left == right) {
        return value[left] * k;
    }

    int middle = (left + right) / 2;
    int leftCount = tree[node * 2].count;

    if (k <= leftCount) {
        return smallestSum(node * 2, left, middle, k);
    }

    return tree[node * 2].sum
         + smallestSum(
               node * 2 + 1,
               middle + 1,
               right,
               k - leftCount
           );
}

// 让线段树恰好保存排序后的前 x 道题。
void movePrefix(int x) {
    while (currentPrefix < x) {
        ++currentPrefix;
        change(
            1, 1, n,
            question[currentPrefix].rank,
            1
        );
    }

    while (currentPrefix > x) {
        change(
            1, 1, n,
            question[currentPrefix].rank,
            -1
        );
        --currentPrefix;
    }
}

// 计算 firstK 到 lastK 的答案。
// 已知这些 k 的最优分界点在 firstCut 到 lastCut 之间。
//
// 调用前、返回后：
// 线段树都恰好保存前 firstCut 道题。
void solve(int firstK, int lastK, int firstCut, int lastCut) {
    if (firstK > lastK) return;

    int k = (firstK + lastK) / 2;

    int bestCut = max(firstCut, k);
    long long bestScore = numeric_limits<long long>::lowest();

    // 前缀里至少需要有 k 道题，所以 x 不能小于 k。
    for (int x = max(firstCut, k); x <= lastCut; ++x) {
        movePrefix(x);

        long long score =
            suffix[x + 1] - smallestSum(1, 1, n, k);

        // 从左往右枚举，只在严格更优时更新。
        // 这样同分时保留最靠左的分界点。
        if (score > bestScore) {
            bestScore = score;
            bestCut = x;
        }
    }

    answer[k] = bestScore;

    // 处理更小的 k。
    movePrefix(firstCut);
    solve(firstK, k - 1, firstCut, bestCut);

    // 左侧递归返回后，前缀仍是 firstCut。
    // 调整到右侧递归需要的初始状态。
    movePrefix(bestCut);
    solve(k + 1, lastK, bestCut, lastCut);

    // 恢复本次调用开始时的状态。
    movePrefix(firstCut);
}

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

    int q;
    cin >> n >> q;

    question.resize(n + 1);
    value.resize(n + 1);
    suffix.assign(n + 2, 0);
    answer.resize(n + 1);
    tree.resize(4 * n + 4);

    for (int i = 1; i <= n; ++i) {
        cin >> question[i].a >> question[i].b;
    }

    // 给每道题分配按 b 排列的编号。
    // 相同的 b 也分配不同编号，不需要去重。
    sort(
        question.begin() + 1,
        question.end(),
        [](const Question& x, const Question& y) {
            return x.b < y.b;
        }
    );

    for (int i = 1; i <= n; ++i) {
        question[i].rank = i;
        value[i] = question[i].b;
    }

    // 正式的题目顺序：按被修改时的损失从大到小排列。
    sort(
        question.begin() + 1,
        question.end(),
        [](const Question& x, const Question& y) {
            return x.a + x.b > y.a + y.b;
        }
    );

    // suffix[i] 表示从第 i 道题到最后一道题的 a 之和。
    for (int i = n; i >= 1; --i) {
        suffix[i] = suffix[i + 1] + question[i].a;
    }

    // 初始前缀为空，符合 firstCut = 0 的要求。
    solve(0, n, 0, n);

    while (q--) {
        int k;
        cin >> k;
        cout << answer[k] << '\n';
    }

    return 0;
}

七、为什么这些来回增删不会太慢？

在一次分治调用中，除去递归内部，前缀来回移动的总距离，只是当前候选分界点区间长度的常数倍。

而在分治的同一层，各个候选区间只共享端点，总长度是 $O(n)$。分治共有 $O(\log n)$ 层。

因此，总共只有 $O(n\log n)$ 次增删，以及 $O(n\log n)$ 次得分计算。每次线段树操作花费 $O(\log n)$，得到：

$$\boxed{\text{时间复杂度 }O(n\log^2 n+q)}$$

只维护一棵普通线段树，其他数组也都是线性大小，因此：

$$\boxed{\text{空间复杂度 }O(n)}$$

最后注意三个边界：$k=0$ 时答案是所有 $a$ 的和；$k=n$ 时答案是所有 $b$ 的和取负；分数和必须使用 long long。

上述实现已通过原题样例，以及 1006 组小规模数据的穷举对拍，对拍枚举了全部答题集合和所有 $k$；也运行了题数为 $2\times10^5$ 的规模测试，但未实际提交在线评测。