233求min - 题解

标签与难度

标签: CDQ分治, 数据结构, 树状数组, 排序, 前缀和, 问题转化难度: 2100

题目大意喵~

主人你好喵~ 这道题是这样的：我们有两个长度都是 $n$ 的序列 $a$ 和 $b$ 。我们需要找到一对下标 $l$ 和 $r$ （其中 $1 \le l \le r \le n$ ），然后计算出从 $l$ 到 $r$ 这段区间的和，分别是序列 $a$ 的区间和以及序列 $b$ 的区间和。

我们的目标，就是要让这两个区间和中较小的那个值尽可能地大！最后，把这个最大的“较小值”输出出来就可以啦，喵~

用数学语言来表达的话，就是要求这个式子的最大值：

\max_{1 \le l \le r \le n} \left( \min \left( \sum_{k=l}^{r} a_k, \sum_{k=l}^{r} b_k \right) \right)

解题思路分析

这道题的目标是“最大化最小值”，一看到这种形式，很多主人的第一反应可能是二分答案，对吧喵？这确实是一条可行的路！但今天本喵想介绍一个更巧妙、更高效的思路，它利用了问题转化和一种叫做“CDQ分治”思想的技巧，不过我们会用一种更容易理解的“排序+树状数组”的方式来实现它，喵~

第一步：前缀和的魔法

首先，每次都去计算 $\sum_{k=l}^{r}$ 是很慢的。对付区间和，我们有强大的武器——前缀和！

我们定义两个前缀和数组 $S_A$ 和 $S_B$ ： $S_A[i] = \sum_{k=1}^{i} a_k$ $S_B[i] = \sum_{k=1}^{i} b_k$

为了方便处理 $l=1$ 的情况，我们让 $S_A[0] = 0$ 和 $S_B[0] = 0$ 。这样，任意区间 $[l, r]$ 的和就可以表示为： $\sum_{k=l}^{r} a_k = S_A[r] - S_A[l-1]$ $\sum_{k=l}^{r} b_k = S_B[r] - S_B[l-1]$

现在，我们的目标变成了：

\max_{0 \le j < i \le n} \left( \min(S_A[i] - S_A[j], S_B[i] - S_B[j]) \right)

这里的 $i$ 对应原来的 $r$ ，而 $j$ 对应原来的 $l-1$ 。

第二步：拆解 `min` 函数

这个 min 函数让问题变得棘手，因为它取决于 $S_A$ 和 $S_B$ 的差值。我们可以把它拆成两种情况来讨论：

对于任意一对 $(i, j)$ ，我们求的值要么是 $S_A[i] - S_A[j]$ ，要么是 $S_B[i] - S_B[j]$ 。

情况一: 当 $S_A[i] - S_A[j] \le S_B[i] - S_B[j]$ 时，我们要求的是 $S_A[i] - S_A[j]$ 的最大值。
情况二: 当 $S_A[i] - S_A[j] > S_B[i] - S_B[j]$ 时，我们要求的是 $S_B[i] - S_B[j]$ 的最大值。

咦？主人你看，情况一和情况二是不是长得很像？它们几乎是完全对称的！如果我们把序列 $a$ 和 $b$ 交换一下，情况一就变成了情况二。这意味着，我们只需要想办法解决其中一种情况，然后把 $a$ 和 $b$ 交换，再跑一遍同样的算法，取两次结果中较大的那个，就是最终答案啦！喵~

第三步：聚焦情况一，变形！

我们来全力解决情况一。目标是：在满足 $j < i$ 和 $S_A[i] - S_A[j] \le S_B[i] - S_B[j]$ 的所有配对 $(i, j)$ 中，找到使 $S_A[i] - S_A[j]$ 最大的那一对。

为了最大化 $S_A[i] - S_A[j]$ ，对于一个固定的 $i$ ，我们自然希望 $S_A[j]$ 越小越好。

我们把条件 $S_A[i] - S_A[j] \le S_B[i] - S_B[j]$ 变形一下，把和 $i$ 相关的项都移到一边，和 $j$ 相关的项移到另一边：

S_A[i] - S_B[i] \le S_A[j] - S_B[j]

为了方便，我们定义一个新的量 $C_k = S_A[k] - S_B[k]$ 。现在，问题就变成了：对于每个 $i \in [1, n]$ ，寻找一个 $j \in [0, i-1]$ ，它需要满足两个条件：

$C_i \le C_j$
$S_A[j]$ 尽可能小

这是一个二维偏序问题：对于每个点 $i$ ，我们要查询满足 $(j < i, C_j \ge C_i)$ 的点 $j$ 中，拥有最小 $S_A[j]$ 的那个。

第四步：排序降维 + 树状数组

这种二维偏序问题，可以用“排序+数据结构”的方法来降维打击！

我们的查询有两个维度： $j<i$ 和 $C_j \ge C_i$ 。我们可以通过一个巧妙的排序来解决掉一个维度。如果我们按照 $C_k$ 的值对所有下标 $k \in [0, n]$ 进行降序排序，那么会发生什么呢？

假设我们按这个顺序来处理每个下标 $i$ 。当我们处理 $i$ 时，所有已经处理过的下标 $j$ 都满足 $C_j \ge C_i$ ！这样， $C_j \ge C_i$ 这个条件就被我们的处理顺序自然地满足了。

现在，对于当前处理的 $i$ ，我们只需要在所有已经处理过并且原始下标满足 $j < i$ 的点中，找到最小的 $S_A[j]$ 。

这不就是一个动态的“查询前缀最小值”问题吗？树状数组（BIT）或者线段树最擅长这个啦！本喵最喜欢用树状数组了，又快又好写，喵~

所以，解决情况一的完整流程就是：

计算前缀和 $S_A, S_B$ 和辅助值 $C_k = S_A[k] - S_B[k]$ ，覆盖下标 $k \in [0, n]$ 。
将所有下标 $k$ 按照 $C_k$ 从大到小排序。如果 $C_k$ 相同，就按 $k$ 从小到大排（这有助于处理边界情况）。
初始化一个树状数组，大小为 $n+2$ ，所有值为一个很大的数（代表正无穷）。
遍历排序后的下标。假设当前处理到的原始下标是 i： a. 在树状数组中查询下标范围 $[1, i]$ （对应原始下标 $[0, i-1]$ ）的最小值，记为 min_SA_j。 b. 如果找到了一个有效的 j（即 min_SA_j 不是无穷大），就用 $S_A[i] - \text{min\_SA\_j}$ 来更新我们的答案。 c. 将 $S_A[i]$ 更新到树状数组的第 $i+1$ 个位置上（因为树状数组下标从1开始）。

这样，我们就漂亮地解决了情况一！

最后，别忘了我们还有情况二。我们把 $a$ 和 $b$ 数组交换一下，重新计算 $S_A, S_B, C$ ，再跑一遍上面的流程，就得到了情况二的答案。两个答案取个最大值，就大功告成啦！

代码实现

这是本喵根据上面的思路，精心重构的代码哦~ 注释很详细，希望能帮到主人，喵~

cpp

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

// 使用 long long 防止前缀和溢出
using ll = long long;

const ll INF = 4e18; // 一个足够大的数，代表无穷大

// 树状数组模板，用于维护前缀最小值
struct FenwickTree {
    vector<ll> bit;
    int size;

    FenwickTree(int n) : size(n + 1), bit(n + 1, INF) {}

    // 更新位置 idx 的值为 val (取较小者)
    void update(int idx, ll val) {
        for (++idx; idx < size; idx += idx & -idx) {
            bit[idx] = min(bit[idx], val);
        }
    }

    // 查询 [0, idx] 范围内的最小值
    ll query(int idx) {
        ll min_val = INF;
        for (++idx; idx > 0; idx -= idx & -idx) {
            min_val = min(min_val, bit[idx]);
        }
        return min_val;
    }
};

// 解决核心问题的函数
ll solve(int n, const vector<ll>& s_a, const vector<ll>& s_b) {
    // 包含了 n+1 个点 (从 0 到 n)
    vector<int> p(n + 1);
    // iota 会用 0, 1, 2, ... 把 p 填满
    iota(p.begin(), p.end(), 0);

    // 计算 C_k = S_A[k] - S_B[k]
    vector<ll> c(n + 1);
    for (int i = 0; i <= n; ++i) {
        c[i] = s_a[i] - s_b[i];
    }

    // 排序！这是降维的关键喵~
    // 按 C_k 降序排，C_k 相同时按 k 升序排
    sort(p.begin(), p.end(), [&](int i, int j) {
        if (c[i] != c[j]) {
            return c[i] > c[j];
        }
        return i < j;
    });

    ll max_val = -INF;
    // 树状数组需要 n+1 个位置 (0 to n), 所以大小是 n+2
    FenwickTree ft(n + 2);

    for (int i : p) {
        // 查询在 i 之前、且满足 C_j >= C_i 的 j 中，S_A[j] 的最小值
        // 排序保证了 C_j >= C_i, 树状数组处理 j < i 的限制
        ll min_sa_j = ft.query(i - 1);

        if (min_sa_j != INF) {
            max_val = max(max_val, s_a[i] - min_sa_j);
        }
        
        // 将当前点的 S_A[i] 加入数据结构，供后续的点查询
        ft.update(i, s_a[i]);
    }

    return max_val;
}

int main() {
    // 加速输入输出，让本喵跑得更快！
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<ll> a(n), b(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < n; ++i) cin >> b[i];

    vector<ll> s_a(n + 1, 0), s_b(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        s_a[i + 1] = s_a[i] + a[i];
        s_b[i + 1] = s_b[i] + b[i];
    }

    // Case 1: max(S_A[i] - S_A[j]) subject to S_A-S_B <= S_A-S_B
    ll ans1 = solve(n, s_a, s_b);

    // Case 2: max(S_B[i] - S_B[j]) subject to S_B-S_A <= S_B-S_A
    // 这等价于交换 a 和 b 再跑一遍
    ll ans2 = solve(n, s_b, s_a);

    cout << max(ans1, ans2) << endl;

    return 0;
}

复杂度分析

时间复杂度: $O(N \log N)$
- 计算前缀和需要 $O(N)$ 的时间。
- solve 函数是复杂度的主要部分。其中，对 $N+1$ 个下标进行排序，需要 $O(N \log N)$ 的时间。
- 之后，我们遍历这 $N+1$ 个排好序的下标，每次在树状数组中进行一次查询和一次更新，每次操作的复杂度是 $O(\log N)$ 。所以循环部分的总复杂度是 $O(N \log N)$ 。
- 我们调用了两次 solve 函数，所以总时间复杂度是 $O(N \log N) + O(N \log N) = O(N \log N)$ ，非常高效，喵！
空间复杂度: $O(N)$
- 我们需要存储前缀和数组 $S_A, S_B$ ，以及辅助数组 $C$ 和下标数组 $p$ ，这些都需要 $O(N)$ 的空间。
- 树状数组也需要 $O(N)$ 的空间。
- 所以总的空间开销是线性的，很节省内存呢。

知识点总结

这道题是一道非常精彩的综合题，融合了多种算法思想，做完之后是不是感觉收获满满呀，喵~

前缀和: 处理区间和问题的基本技巧，能将 $O(N)$ 的查询优化到 $O(1)$ 。
问题转化与分类讨论: 面对复杂的 min 或 max 约束时，一个强大的思路是将其拆解成几种更简单的情况。这道题里，我们利用对称性，将问题一分为二，大大简化了逻辑。
排序降维: 这是解决多维偏序问题的核心思想。通过对一个维度进行排序，我们可以消除这个维度的约束，将问题降低一个维度，从而用更简单的数据结构（如树状数组）解决。
树状数组 (Fenwick Tree): 维护前缀信息（和、最值等）的利器。它在动态查询“前缀X”问题上，提供了 $O(\log N)$ 的优秀性能，而且代码实现比线段树更简洁。

希望本喵的题解能帮助主人更好地理解这道题！继续加油哦，每一道AC的题目都是你成长的见证，喵~ 💕

233求min - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

第一步：前缀和的魔法 ​

第二步：拆解 min 函数 ​

第三步：聚焦情况一，变形！ ​

第四步：排序降维 + 树状数组 ​

代码实现 ​

复杂度分析 ​

知识点总结 ​