NekoNowcoder

Appearance

Removing Stones - 题解 ​

标签与难度 ​

标签: 分治, RMQ, 稀疏表(ST表), 二分查找, 前缀和, 构造 难度: 2200

游戏规则解析喵~ ​

各位看官，大家好呀！我是你们最爱算法的我，喵~ 🐾 今天我们要解决一个关于搬石头的有趣问题，呐。

Alice 给 Mark 设计了一个游戏：有 NN 堆石头，第 ii 堆有 aia_i 个。Mark 的目标是拿走所有石头。每次操作，他可以选择两堆不同的、且都非空的石子堆，并从这两堆中各拿走一个石头。

如果最后能把所有石头都拿完，Mark 就赢啦。但是，如果总石头数是奇数，一开始就赢不了呀，因为每次都拿走 2 个。所以有个特殊规则：如果初始总石头数是奇数，Mark 会在游戏开始前，从数量最少的石堆中拿走一个石头，让总数变成偶数。

我们的任务是，对于一个初始的石头序列 a1,a2,…,aNa_1, a_2, \ldots, a_N，计算有多少对 (l,r)(l, r)（其中 1≤l<r≤N1 \le l < r \le N），使得只用 ll 到 rr 的这些石堆玩游戏时，Mark 能够获胜。

解题思路分析 ​

这道题看起来有点复杂，但别怕，跟着我一步步来分析，很快就能找到线索的喵~

Step 1: 胜利的条件是什么喵？ ​

首先，我们来思考一下，对于一个给定的石子堆集合，怎么样才能算赢呢？

每次操作我们都会拿走 2 个石头，所以游戏能进行下去直到结束，总石头数必须是偶数。题目已经贴心地帮我们处理了初始总数为奇数的情况。

那么，在一个总数为偶数的石子堆集合里，胜利的充要条件是什么呢？ 让我们把数量最多的那堆石头单独拎出来，设它的数量是 MM。其他所有石头的总数就是 S−MS - M，其中 SS 是所有石头的总和。

在每次操作中，如果我们想减少 MM 的数量，就必须从另外一堆石头里也拿一个。所以，为了把数量为 MM 的这堆石头拿完，我们最多可以把它和其他石头配对 S−MS - M 次。

  • 如果 M>S−MM > S - M，也就是 2M>S2M > S，那么即使我们把其他所有石头都用来和这堆最多的配对，它依然会有剩余。这样就输啦，呜呜~
  • 如果 M≤S−MM \le S - M，也就是 2M≤S2M \le S，那么我们总有办法把所有石头拿完。我们可以一直从当前最多的两堆中拿石头，或者从最多的一堆和任意一堆非空的拿，这样可以保证不会出现 M>S−MM > S - M 的情况，最终一定能赢！

所以，对于一个总数为偶数的石子堆集合，胜利的条件是：数量最多的石堆的大小，不超过所有其他石堆大小的总和。用数学公式表达就是：

2×M≤S2 \times M \le S

Step 2: 统一奇偶情况的条件！ ​

现在我们来考虑题目中的奇偶数规则。对于一个区间 [l,r][l, r]：

  • 如果 ∑i=lrai\sum_{i=l}^{r} a_i 是偶数：游戏直接开始。设 Sl,r=∑i=lraiS_{l,r} = \sum_{i=l}^{r} a_i，Ml,r=max⁡i=lraiM_{l,r} = \max_{i=l}^{r} a_i。胜利条件就是 2×Ml,r≤Sl,r2 \times M_{l,r} \le S_{l,r}。
  • 如果 ∑i=lrai\sum_{i=l}^{r} a_i 是奇数：游戏开始前，要从最少的石堆里拿掉一个。新的总数变成 Sl,r′=Sl,r−1S'_{l,r} = S_{l,r} - 1（这是一个偶数）。新的最大值 Ml,r′M'_{l,r} 最多也就是原来的 Ml,rM_{l,r}（因为我们是从最小堆拿的，一般不会影响最大堆）。胜利条件是 2×Ml,r′≤Sl,r′2 \times M'_{l,r} \le S'_{l,r}。因为 Ml,r′≤Ml,rM'_{l,r} \le M_{l,r}，所以一个充分条件是 2×Ml,r≤Sl,r−12 \times M_{l,r} \le S_{l,r} - 1。

这两种情况看起来不一样，好麻烦呀！但是，我发现了一个小秘密，喵~ ✨ 当 Sl,rS_{l,r} 是奇数时，我们来研究一下 2×Ml,r≤Sl,r2 \times M_{l,r} \le S_{l,r} 这个不等式。 2×Ml,r2 \times M_{l,r} 必然是个偶数，而 Sl,rS_{l,r} 是个奇数。一个偶数和一个奇数永远不可能相等！ 所以，如果 Sl,rS_{l,r} 是奇数，那么不等式 2×Ml,r≤Sl,r2 \times M_{l,r} \le S_{l,r} 其实等价于 2×Ml,r≤Sl,r−12 \times M_{l,r} \le S_{l,r} - 1。

哇！这也就是说，不管 Sl,rS_{l,r} 是奇数还是偶数，胜利的条件都可以统一成一个简单的形式：

2×max⁡i=lrai≤∑i=lrai2 \times \max_{i=l}^{r} a_i \le \sum_{i=l}^{r} a_i

这真是太棒了！问题一下子清晰多啦！

Step 3: 从暴力到分治的飞跃！ ​

现在我们的目标就是统计满足 2×Ml,r≤Sl,r2 \times M_{l,r} \le S_{l,r} 的配对 (l,r)(l, r) 的数量。

一个最直接的想法是枚举所有的 (l,r)(l, r)，然后对每个区间计算最大值和总和。这需要 O(N2)O(N^2) 的时间，对于 NN 这么大的数据量，肯定会超时的说。

我们需要更快的算法！这种和区间最值有关的计数问题，一个非常强大的武器就是分治！

我们可以把分治的中心放在区间的最大值上。 假设我们处理一个大区间 [L, R]。我们先找到这个区间里最大值 a[k] 的位置 k。 那么，任何一个包含 a[k] 作为其最大值的子区间 [l, r]，都必须满足 L <= l <= k <= r <= R。

这样，我们就把问题分成了三部分：

  1. 左端点在 [L, k-1]，右端点在 [k+1, R] 的区间（这些区间不包含a[k]，最大值在别处）。
  2. 左端点在 [L, k]，右端点在 [k, R] 的区间（这些是跨过 k 的区间，它们的最大值就是 a[k]）。
  3. 只在 [L, k-1] 内部的区间。
  4. 只在 [k+1, R] 内部的区间。

第3和第4部分可以通过递归 solve(L, k-1) 和 solve(k+1, R) 来解决。 我们的核心任务，就是在当前这层分治中，解决第2部分：计算所有跨过 k 且满足条件的区间 (l, r)。

对于这些跨过 k 的区间 [l, r]，我们已经知道了最大值是 Ml,r=akM_{l,r} = a_k。 条件就变成了 2×ak≤Sl,r2 \times a_k \le S_{l,r}。 为了方便计算区间和，我们可以预处理一个前缀和数组 sum，其中 sum[i] = a[1] + ... + a[i]。这样 Sl,r=sum[r]−sum[l−1]S_{l,r} = \text{sum}[r] - \text{sum}[l-1]。 条件就是: 2×ak≤sum[r]−sum[l−1]2 \times a_k \le \text{sum}[r] - \text{sum}[l-1]。

为了高效地计数，我们可以采用一个经典优化：启发式合并/小大合并。 我们比较 k 左边 [L, k-1] 和右边 [k+1, R] 的长度。我们遍历较短的那一边，然后在较长的那一边用二分查找来寻找合法的配对。

举个例子，假设左边 [L, k-1] 比较短： 我们遍历 l 从 L 到 k。对于每一个固定的 l，我们要找有多少个 r（k <= r <= R）满足：

sum[r]≥sum[l−1]+2×ak\text{sum}[r] \ge \text{sum}[l-1] + 2 \times a_k

因为前缀和数组 sum 是单调递增的，所以右边的 sum[k], sum[k+1], ..., sum[R] 也是单调递增的。我们可以直接在 sum 数组的 [k, R] 这个下标范围内，二分查找出第一个满足条件的 r 的位置。那么从这个位置到 R 的所有 r 都满足条件，可以直接计数！

Step 4: 算法实现细节喵~ ​

  1. 预处理：

    • 计算前缀和数组 sum。记得用 long long 防止溢出哦！
    • 为了能快速查询任意区间的最大值位置 k，我们可以用稀疏表（ST表）。预处理需要 O(Nlog⁡N)O(N \log N)，查询是 O(1)O(1)。

  2. 分治函数 solve(L, R)：

    • 递归出口: 如果 L >= R，说明区间太小了，形不成 l < r 的配对，直接返回。
    • 找最大值: 用ST表查询 [L, R] 区间最大值的位置 k。
    • 启发式计数:
      • 比较 k-L 和 R-k 的大小。
      • 遍历短的一侧（比如左侧 l 从 L 到 k），计算出 target = sum[l-1] + 2LL * a[k]。
      • 在长的一侧（右侧 r 从 k 到 R）对应的 sum 数组上二分查找（lower_bound），找到满足 sum[r] >= target 的 r 的数量。
      • 累加到最终答案 ans。
    • 递归: 调用 solve(L, k-1) 和 solve(k+1, R)。

整个算法的复杂度分析下来，是 O(Nlog⁡2N)O(N \log^2 N) 的。对于本题的数据范围来说，已经足够快啦！

代码实现 ​

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

using namespace std;

// 使用 long long 防止求和时溢出
using ll = long long;

const int MAXN = 300005;
const int LOGN = 19;

int n;
int a[MAXN];
ll prefix_sum[MAXN];

// st[i][j] 存储区间 [i, i + 2^j - 1] 中最大值的下标
int st[MAXN][LOGN];

// 预处理ST表，用于快速查询区间最大值 (RMQ)
void build_st() {
    for (int i = 1; i <= n; ++i) {
        st[i][0] = i;
    }
    for (int j = 1; (1 << j) <= n; ++j) {
        for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
            int idx1 = st[i][j - 1];
            int idx2 = st[i + (1 << (j - 1))][j - 1];
            if (a[idx1] >= a[idx2]) {
                st[i][j] = idx1;
            } else {
                st[i][j] = idx2;
            }
        }
    }
}

// 查询区间 [l, r] 中最大值的下标
int query_max_idx(int l, int r) {
    int k = log2(r - l + 1);
    int idx1 = st[l][k];
    int idx2 = st[r - (1 << k) + 1][k];
    if (a[idx1] >= a[idx2]) {
        return idx1;
    } else {
        return idx2;
    }
}

ll ans = 0;

// 分治解决问题
void solve(int l, int r) {
    // 递归出口：区间长度小于2，无法构成 l < r 的配对
    if (l >= r) {
        return;
    }

    // 找到当前区间的最大值及其下标
    int max_idx = query_max_idx(l, r);
    ll max_val = a[max_idx];

    // 启发式合并：遍历短的一侧，在长的一侧二分查找
    if (max_idx - l < r - max_idx) {
        // 左半部分 [l, max_idx] 较短
        for (int i = l; i <= max_idx; ++i) {
            ll target = prefix_sum[i - 1] + 2 * max_val;
            // 在右半部分 [max_idx, r] 中查找满足条件的 r
            // lower_bound 返回第一个不小于 target 的元素的迭代器
            auto it = lower_bound(prefix_sum + max_idx, prefix_sum + r + 1, target);
            // 计算有多少个 r 满足条件
            ans += (prefix_sum + r + 1) - it;
        }
    } else {
        // 右半部分 [max_idx, r] 较短或等长
        for (int j = max_idx; j <= r; ++j) {
            ll target = prefix_sum[j] - 2 * max_val;
            // 在左半部分 [l, max_idx] 中查找满足条件的 l
            // upper_bound 返回第一个大于 target 的元素的迭代器
            // 它的位置索引就等于 <= target 的元素个数
            auto it = upper_bound(prefix_sum + l - 1, prefix_sum + max_idx, target);
            ans += (it - (prefix_sum + l - 1));
        }
    }

    // 递归处理左右两个子区间
    solve(l, max_idx - 1);
    solve(max_idx + 1, r);
}

void run_case() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    // 预处理前缀和
    prefix_sum[0] = 0;
    for (int i = 1; i <= n; ++i) {
        prefix_sum[i] = prefix_sum[i - 1] + a[i];
    }

    // 构建ST表
    build_st();

    // 开始分治
    ans = 0;
    solve(1, n);

    cout << ans << endl;
}

int main() {
    // 加速输入输出，喵~
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    while (t--) {
        run_case();
    }
    return 0;
}

复杂度分析 ​

  • 时间复杂度: O(Nlog⁡2N)O(N \log^2 N)

    • 预处理前缀和是 O(N)O(N)。
    • 预处理ST表是 O(Nlog⁡N)O(N \log N)。
    • 分治函数 solve 是核心。在每一层分治中，我们把一个区间分成两半，然后遍历较小的一半，对每个元素在较大的一半里做一次二分查找。一个元素在分治过程中，它所在的区间大小每次至少减半，所以它最多只会被归入“较小的一半” O(log⁡N)O(\log N) 次。每次作为“小半”的元素，需要进行一次 O(log⁡N)O(\log N) 的二分查找。所以总的时间复杂度是 O(Nlog⁡2N)O(N \log^2 N)。

  • 空间复杂度: O(Nlog⁡N)O(N \log N)

    • 前缀和数组占 O(N)O(N)。
    • ST表占 O(Nlog⁡N)O(N \log N) 的空间。
    • 递归栈的深度最多是 O(N)O(N)，但在平衡情况下是 O(log⁡N)O(\log N)。
    • 所以总空间复杂度由ST表决定，为 O(Nlog⁡N)O(N \log N)。

知识点总结 ​

这道题真是一次有趣的冒险，喵~ 我们用到了不少好玩的工具呢：

  1. 问题转化与构造: 最关键的一步是发现无论区间和是奇是偶，胜利条件都能统一为 2×M≤S2 \times M \le S。这是解题的突破口！
  2. 分治思想: 特别是基于最值的分治，是处理与区间最值相关问题的常用且强大的技巧。
  3. 启发式合并 (Smaller-to-larger): 在分治中，通过总是处理较小的一半来优化整体复杂度，这是一个非常重要的思想。
  4. 数据结构组合拳: 我们用前缀和来快速处理区间和，用**稀疏表(ST表)**来快速处理区间最大值查询，两者结合为分治提供了强大的火力支援！
  5. 二分查找: 在有序序列中寻找满足条件的元素数量，二分查找是我们的不二之选。

希望这篇题解能帮助你更好地理解这个问题，喵~ 如果你喜欢，就给我点个赞吧！我们下次再见，拜拜~ 🐾