F. Yamakasi - 题解

比赛与标签

比赛: Codeforces Round 1032 (Div. 3) 标签: binary search, brute force, data structures, greedy, two pointers 难度: *1800

题目大意喵~

主人，这道题是说呀，给我们一个整数数组 a，还有两个整数 s 和 x。我们的任务是，找出这个数组里有多少个连续的子数组（也叫子区段），同时满足下面这两个条件哦：

子数组里所有数字加起来的和，正好等于 s。
子数组里最大的那个数字，正好等于 x。

我们要数出所有满足条件的子数组的数量，然后告诉裁判就可以啦！是不是听起来很有趣呀？

解题思路详解喵！

这道题有两个条件需要同时满足：和为 s 并且 最大值为 x。直接同时处理这两个条件会有点棘手呢，呐。

当遇到“正好等于”这种苛刻的条件时，一个非常强大的思路就是容斥原理（Inclusion-Exclusion Principle）！我们可以把问题转化一下：

[最大值恰好为 x 的方案数] = [最大值至多为 x 的方案数] - [最大值严格小于 x 的方案数]

为什么可以这么做呢？

“最大值至多为 x” 意味着子数组里所有元素都 ≤ x。
“最大值严格小于 x” 意味着子数组里所有元素都 < x。
两者相减，剩下的不就是那些“所有元素都 ≤ x，并且至少有一个元素等于 x”的方案嘛？这正好就是“最大值为 x”的定义呀！喵~

这样一转换，问题就变得清晰多啦！

第一步：处理 `max <= x` 的情况

要让子数组的最大值 ≤ x，那么这个子数组里就不能有任何 > x 的元素。这些 > x 的元素就像一道道高墙，把我们的原数组分成了好几个小段。所有满足 max <= x 的子数组，都必须完整地存在于这些小段之中。

所以，我们可以遍历整个数组，以所有 > x 的元素为分界点，把数组切分成若干个“合法”的区块。在每个区块内，所有元素的数值都 ≤ x。

第二步：处理 `max < x` 的情况

同理，要让子数组的最大值 < x，那么这个子数组里就不能有任何 ≥ x 的元素。也就是说，所有元素都必须严格 < x。这和上一步很像！在我们上一步划分出的“合法”区块（所有元素 ≤ x）内部，那些等于 x 的元素又成了新的分界点。它们会把一个大区块，再切分成更小的“次级区块”。在这些次级区块里，所有元素的数值都严格 < x。

第三.五步：如何在区块内快速计算和为 `s` 的子数组数量？

现在我们的问题简化为：在一个给定的数组区块内，计算有多少个子数组的和为 s。这是一个非常经典的问题，可以用 前缀和 + 哈希表 的方法在近似线性的时间内解决！

前缀和 (Prefix Sum)：我们先计算出数组的前缀和 p，其中 p[i] 表示原数组 a[0]...a[i-1] 的和。那么，子数组 a[l...r] 的和就可以用 p[r+1] - p[l] 快速得到。
哈希表 (Hash Map)：我们想要找到满足 p[r+1] - p[l] = s 的 (l, r) 对。变形一下就是 p[l] = p[r+1] - s。
我们可以遍历区块的右端点 r（对应前缀和数组的 i = r+1），对于每个 i，我们想知道在它左边有多少个 j（对应 l），使得 p[j] 等于我们计算出的目标值 p[i] - s。用一个哈希表来记录之前出现过的所有前缀和 p[j] 的次数，就可以 O(1) 查询啦！

最终整合！

我们的完整策略就是：

以 > x 的元素为界，将原数组分割成多个区块。
对每个区块，使用“前缀和+哈希表”的方法，计算出其中和为 s 的子数组数量。把这些数量全部加起来，得到 count1（这就是 max <= x 的情况）。
在每个区块内部，再以 == x 的元素为界，分割成更小的子区块。
对每个子区块，同样用“前缀和+哈希表”计算和为 s 的子数组数量。把这些数量全部加起来，得到 count2（这就是 max < x 的情况）。
最终的答案就是 count1 - count2！完美~

代码实现喵~

cpp

#include <iostream>
#include <vector>
#include <numeric>
#include <unordered_map>
#include <chrono>

// 为了防止哈希碰撞被卡，写一个自定义的哈希函数，这是一个好习惯哦，喵~
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(long long x) const {
        static const uint64_t FIXED_RANDOM = std::chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

void solve() {
    int n;
    long long s, x;
    std::cin >> n >> s >> x;
    std::vector<long long> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }

    // 预处理前缀和数组，p[i] 存 a[0]...a[i-1] 的和
    std::vector<long long> p(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        p[i + 1] = p[i] + a[i];
    }

    // 这是一个lambda函数，用来计算在原数组 a 的 [l, r] 范围内，和为 s 的子数组数量
    auto count_in_range = [&](int l, int r) {
        if (l > r) return 0LL; // 如果范围无效，直接返回0
        std::unordered_map<long long, int, custom_hash> freqs;
        long long current_count = 0;
        
        // 子数组的起点可以是l，对应的前缀和是p[l]。我们先把它放进哈希表
        freqs[p[l]] = 1;
        
        // 遍历子数组的终点 i (从 l 到 r)
        for (int i = l; i <= r; ++i) {
            // 子数组 a[k...i] 的和是 p[i+1] - p[k] = s
            // 我们需要找的前缀和 p[k] = p[i+1] - s
            long long target = p[i + 1] - s;
            if (freqs.count(target)) {
                current_count += freqs.at(target);
            }
            // 把当前终点的前缀和 p[i+1] 加入哈希表，供后面的终点使用
            freqs[p[i + 1]]++;
        }
        return current_count;
    };

    long long total_count = 0;
    int last_gt = -1; // 记录上一个 > x 的元素的位置
    
    // 遍历数组，以 > x 的元素为分界点
    for (int i = 0; i <= n; ++i) {
        // 当 i == n (数组末尾) 或 a[i] > x 时，表示一个区块 [last_gt + 1, i - 1] 结束了
        if (i == n || a[i] > x) {
            int block_l = last_gt + 1;
            int block_r = i - 1;
            
            if (block_l <= block_r) {
                // [Inclusion/容] 计算这个区块内所有和为 s 的子数组 (此时 max <= x)
                total_count += count_in_range(block_l, block_r);

                // [Exclusion/斥] 减去那些 max < x 的情况
                int last_eq_x = last_gt; // 记录上一个 == x 的元素的位置
                // 在当前区块内，再以 == x 的元素为分界点
                for (int j = last_gt + 1; j <= i; ++j) {
                    if (j == i || a[j] == x) {
                        int sub_block_l = last_eq_x + 1;
                        int sub_block_r = j - 1;
                        if (sub_block_l <= sub_block_r) {
                             // 这个子区块内所有元素都 < x，计算其中和为 s 的子数组数量并减去
                             total_count -= count_in_range(sub_block_l, sub_block_r);
                        }
                        last_eq_x = j;
                    }
                }
            }
            last_gt = i; // 更新分界点位置
        }
    }
    std::cout << total_count << "\n";
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

复杂度分析的说

时间复杂度: O(N) 的说。虽然代码里有嵌套循环，但仔细看呐，外层循环以 > x 的元素为界，内层循环以 == x 的元素为界。count_in_range 函数会遍历它负责的区间。每个数组元素 a[i] 最多被 count_in_range 访问两次：一次是在计算 max <= x 的大区块时（计入总数），一次是在计算 max < x 的小区块时（从总数中减去）。哈希表的单次操作平均是 O(1)。所以，总的时间复杂度与遍历数组两次是相当的，也就是 O(N) 啦！
空间复杂度: O(N) 的说。我们用了一个前缀和数组 p，大小为 N+1。在 count_in_range 函数中，哈希表 freqs 在最坏情况下可能需要存储区块内所有不同的前缀和，大小也可能是 O(N) 的级别。所以总的空间复杂度是 O(N)。

知识点与总结喵~

这道题真是个宝藏，教会了我们好多东西呢！

容斥原理 (Inclusion-Exclusion): 解决“恰好等于”问题的黄金法则！把复杂约束分解成几个更简单的“至多/至少”的约束，然后加加减减得到答案。这是组合数学里非常重要的思想，要牢牢记住哦！
前缀和 + 哈希表: 这是在数组中查找特定和的子数组/子序列的“标准配置”，速度快，效果好，一定要熟练掌握的说。
分治思想 (Divide and Conquer): 利用不满足条件的元素（>x 或 ==x）作为“墙壁”，将大问题分解成一个个独立的小问题。这种分割问题的思路在很多题目里都非常有用。
自定义哈希 (Custom Hash): 在 C++ 的 unordered_map 中，当键是整数时，默认哈希函数在某些特定数据下可能会产生大量冲突，导致性能退化到 O(N)。写一个带随机种子的自定义哈希函数可以有效地避免这种情况，是竞赛中的一个实用小技巧！

希望这篇题解能帮助到主人哦！如果还有不明白的地方，随时可以再来问猫娘我呀！我们一起努力，变得更强，喵~！

F. Yamakasi - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路详解喵！ ​

第一步：处理 max <= x 的情况 ​

第二步：处理 max < x 的情况 ​

第三.五步：如何在区块内快速计算和为 s 的子数组数量？ ​

最终整合！ ​

代码实现喵~ ​

复杂度分析的说 ​

知识点与总结喵~ ​