NekoNowcoder

Appearance

GreaterandGreater - 题解 ​

标签与难度 ​

标签: bitset, 排序, 双指针, 算法优化, 卷积思想 难度: 2000

题目大意喵~ ​

主人你好呀，喵~ 这是一道关于序列匹配的题目哦！

我们有两个序列，AA (长度为 nn) 和 BB (长度为 mm)。你的任务是，找出在序列 AA 中，有多少个长度为 mm 的连续子序列 SS，能够满足一个特殊的条件。这个条件就是：对于子序列 SS 中的每一个元素 SiS_i，它都必须大于或等于序列 BB 中对应位置的元素 BiB_i。

换句话说，我们要找到所有满足条件的起始位置 kk（0≤k≤n−m0 \le k \le n-m），使得对于所有的 jj（0≤j<m0 \le j < m），都有 A[k+j]≥B[j]A[k+j] \ge B[j] 成立。最后，我们要数一数这样合格的起始位置 kk 有多少个，然后告诉我就好啦，喵！

举个栗子： A={3,4,5,1,2}A = \{3, 4, 5, 1, 2\}, n=5n=5B={1,2,3}B = \{1, 2, 3\}, m=3m=3

  • 从 k=0k=0 开始的子序列 SS 是 {3,4,5}\{3, 4, 5\}。

    • S0=3≥B0=1S_0=3 \ge B_0=1 (Ok)
    • S1=4≥B1=2S_1=4 \ge B_1=2 (Ok)
    • S2=5≥B2=3S_2=5 \ge B_2=3 (Ok)
    • 所有条件都满足，所以 k=0k=0 是一个合格的起始位置！

  • 从 k=1k=1 开始的子序列 SS 是 {4,5,1}\{4, 5, 1\}。

    • S2=1<B2=3S_2=1 < B_2=3 (不行啦！)
    • k=1k=1 不合格。

  • 从 k=2k=2 开始的子序列 SS 是 {5,1,2}\{5, 1, 2\}。

    • S1=1<B1=2S_1=1 < B_1=2 (也不行喵...)
    • k=2k=2 不合格。

所以，这组样例里只有一个合格的起始位置，答案就是 1 啦！

解题思路分析 ​

这道题如果直接用爪子去一个一个地试，可能会很慢哦。让我们一起来想个聪明的办法吧，喵~

1. 朴素的想法 ​

最直接的想法就是，我们遍历所有可能的起始位置 kk（从 00 到 n−mn-m），对于每一个 kk，我们再检查它对应的子序列 A[k..k+m−1]A[k..k+m-1] 是否满足条件。

cpp
// 伪代码喵~
count = 0
for k from 0 to n-m:
  is_valid = true
  for j from 0 to m-1:
    if A[k+j] < B[j]:
      is_valid = false
      break
  if is_valid:
    count++

这个方法的时间复杂度是 O((n−m+1)⋅m)O((n-m+1) \cdot m)，大约是 O(n⋅m)O(n \cdot m)。如果 nn 和 mm 都很大（比如 10510^5），那我们的电脑猫爪就会算到冒烟也算不完的！所以，必须得想个更快的办法，呐。

2. 换个角度看问题 ​

一个起始位置 kk 是合格的，当且仅当 所有 的 j∈[0,m−1]j \in [0, m-1] 都满足 A[k+j]≥B[j]A[k+j] \ge B[j]。

这句话听起来像废话，但它很重要！我们可以把它想象成：对于一个起始位置 kk，它需要通过 mm 个独立的考验，每个考验由 BjB_j 给出。只有通过全部 mm 个考验的 kk，才是我们想要的。

我们可以把所有可能的起始位置 kk 看成一个集合，一开始，所有 k∈[0,n−m]k \in [0, n-m] 都是“待定”的。然后，我们对每个 j∈[0,m−1]j \in [0, m-1] 进行一次筛选：

  • 对于考验 jj（由 BjB_j 决定），我们淘汰掉所有不满足 A[k+j]≥BjA[k+j] \ge B_j 的 kk。

经过全部 mm 轮筛选后，剩下的 kk 就是最终的答案。

3. bitset 加速魔法！ ​

“筛选”这个操作，听起来就像是集合求交集，对吧？而 bitset 就是处理这种事情的超级魔法工具！它可以非常快地对一长串的 0 和 1 进行位运算。

让我们用一个 bitset valid_shifts 来记录哪些起始位置 kk 是合格的。valid_shifts[k] 为 1 表示 kk 目前仍然是合格候选，为 0 表示已经被淘汰。我们一开始把 valid_shifts 的所有位都设为 1。

现在，我们来考虑第 jj 个考验：A[k+j]≥BjA[k+j] \ge B_j。 我们怎么用 bitset 来表示所有满足这个特定考验的 kk 呢？

首先，我们可以创建一个辅助 bitset，叫 is_A_large_enough。is_A_large_enough[i] = 1 表示 AiA_i 的值大于等于我们当前考验的值 BjB_j。

is_A_large_enough[i]={1if A[i]≥B[j]0if A[i]<B[j]\text{is\_A\_large\_enough}[i] = \begin{cases} 1 & \text{if } A[i] \ge B[j] \\ 0 & \text{if } A[i] < B[j] \end{cases}

有了这个 bitset，我们怎么得到满足 A[k+j]≥BjA[k+j] \ge B_j 的所有 kk 呢？ 仔细看，is_A_large_enough[k+j] 是 1 就代表满足条件。 这正好对应 bitset 的右移操作！ 如果我们将 is_A_large_enough 右移 jj 位，那么新的 bitset 的第 kk 位，正好就是原来 is_A_large_enough 的第 k+jk+j 位！

所以，对于第 jj 个考验，满足条件的 kk 集合可以用 (is_A_large_enough >> j) 来表示。

现在我们的算法思路清晰多啦：

  1. 初始化 valid_shifts 全为 1。
  2. 对每一个 j∈[0,m−1]j \in [0, m-1]: a. 构建一个临时的 bitset is_A_large_enough，其中 is_A_large_enough[i] = 1 当且仅当 A[i]≥B[j]A[i] \ge B[j]。 b. 将这个临时 bitset 右移 jj 位，得到一个 mask。 c. valid_shifts &= mask。
  3. 最后，valid_shifts.count() 就是答案。

但是... 等等喵！在第 2.a 步，为每个 BjB_j 都重新构建一次 is_A_large_enough 还是需要 O(n)O(n) 的时间，总时间复杂度依然是 O(n⋅m)O(n \cdot m)。魔法好像还不够强力呀！

4. 终极优化：排序与双指针 ​

别灰心，我们离成功只有一步之遥了！关键在于如何高效地构建那一系列的 is_A_large_enough。

注意到，如果一个数 AiA_i 大于等于 v1v_1，那它肯定也大于等于任何比 v1v_1 小的数 v2v_2。 这启发我们，可以按 BjB_j 的值来处理这些考验！

让我们把 AA 和 BB 中的元素都存成 (值, 原始下标) 的形式，然后分别按值的大小进行排序。

  • sorted_A: (A_i, i) 按 A_i 排序。
  • sorted_B: (B_j, j) 按 B_j 排序。

现在，我们从大到小处理 sorted_B 中的每个元素 (B_j, j)。同时，我们维护一个 bitset possible_A_indices，它表示当前有哪些位置的 AA 元素，其值大于等于我们正在处理的 BjB_j。

我们用两个指针，一个指向 sorted_B（从末尾开始，值最大），一个指向 sorted_A（也从末尾开始，值最大）。

当我们处理 sorted_B 的第 ii 个元素 (B_val, B_idx) 时：

  1. 我们移动 sorted_A 的指针，把所有值大于等于 B_val 的 A 元素 (A_val, A_idx) 找出来。
  2. 将这些 A_idx 对应的位置在 possible_A_indices 中设为 1。
  3. 因为我们是按 B 值从大到小处理的，所以之前为 possible_A_indices 添加的位这次依然有效，不需要清空。这个 possible_A_indices 正是我们在上一节中梦寐以求的高效构建的 is_A_large_enough！
  4. 然后，我们进行相同的操作：valid_shifts &= (possible_A_indices >> B_idx)。

两个指针都只会从头到尾（或者尾到头）扫一遍，所以这部分的复杂度是 O(n+m)O(n+m)。排序需要 O(nlog⁡n+mlog⁡m)O(n \log n + m \log m)。bitset 操作每次是 O(n/w)O(n/w)（其中 ww是计算机字长，比如64），总共是 O(m⋅n/w)O(m \cdot n/w)。这已经足够快，可以通过题目了！

最终，valid_shifts 中为 1 的位的数量就是答案。而且，聪明的 bitset 会自动处理好边界情况。如果一个起始位置 k>n−mk > n-m，那么在检查某个 jj 时，索引 k+jk+j 必然会超出 AA 的范围（即大于 n−1n-1），possible_A_indices[k+j] 自然是 0，所以 valid_shifts[k] 也就会变成 0。所以最后直接 valid_shifts.count() 就好啦！

代码实现 ​

这是我根据上面的思路，用爪子敲出来的代码哦，希望能帮到你，喵~

cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <bitset>

// 定义一个比较大的值作为 bitset 的大小，确保不会越界
// n 和 m 最大是 150000，所以 bitset 大小设为 150001 就很安全了
const int MAX_SIZE = 150001;

int main() {
    // 使用 C++ 标准 IO 加速，让程序跑得像猫一样快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n, m;
    std::cin >> n >> m;

    // 使用 pair 来存储 (值, 原始下标)
    std::vector<std::pair<int, int>> a(n);
    std::vector<std::pair<int, int>> b(m);

    for (int i = 0; i < n; ++i) {
        std::cin >> a[i].first;
        a[i].second = i;
    }
    for (int i = 0; i < m; ++i) {
        std::cin >> b[i].first;
        b[i].second = i;
    }

    // 分别对 a 和 b 按值升序排序
    std::sort(a.begin(), a.end());
    std::sort(b.begin(), b.end());

    // valid_shifts[k] = 1 表示起始位置 k 是一个可能的解
    // 初始化时，我们假设所有可能的起始位置都是解
    std::bitset<MAX_SIZE> valid_shifts;
    valid_shifts.set(); // 全部置为 1

    // possible_A_indices[i] = 1 表示 A[i] 的值足够大，可以满足当前 B 的约束
    std::bitset<MAX_SIZE> possible_A_indices;

    // 双指针：
    // a_ptr 指向 sorted_a 的末尾（值最大的元素）
    // b_ptr 指向 sorted_b 的末尾（值最大的元素）
    int a_ptr = n - 1;
    for (int b_ptr = m - 1; b_ptr >= 0; --b_ptr) {
        int current_b_value = b[b_ptr].first;
        int current_b_index = b[b_ptr].second;

        // 移动 a_ptr，将所有值 >= current_b_value 的 A 元素的下标加入 bitset
        while (a_ptr >= 0 && a[a_ptr].first >= current_b_value) {
            possible_A_indices[a[a_ptr].second] = 1;
            a_ptr--;
        }

        // 现在 possible_A_indices 代表了所有能满足 B[current_b_index] 约束的 A 元素位置
        // 将其右移 current_b_index 位，得到的 mask 的第 k 位就表示 A[k + current_b_index] 是否满足约束
        // 与总结果求交集，淘汰掉不满足当前约束的 k
        valid_shifts &= (possible_A_indices >> current_b_index);
    }

    // 所有不满足 k <= n-m 的 k 对应的位都会在计算过程中被自动清零
    // 所以可以直接统计结果
    std::cout << valid_shifts.count() << std::endl;

    return 0;
}

复杂度分析 ​

  • 时间复杂度: O(nlog⁡n+mlog⁡m+m⋅n/w)O(n \log n + m \log m + m \cdot n/w)

    • 对序列 AA 和 BB 排序分别需要 O(nlog⁡n)O(n \log n) 和 O(mlog⁡m)O(m \log m)。
    • 双指针和 bitset 操作的循环总共执行 mm 次。在循环中，双指针 a_ptr 总共移动 O(n)O(n) 次。bitset 的位移和与操作的复杂度是 O(n/w)O(n/w)，其中 ww 是计算机的字长（通常是64）。所以这部分总复杂度是 O(n+m⋅n/w)O(n + m \cdot n/w)。
    • 综合起来，排序是主要瓶颈之一，所以总时间复杂度为 O(nlog⁡n+mlog⁡m+m⋅n/w)O(n \log n + m \log m + m \cdot n/w)。

  • 空间复杂度: O(n+m)O(n+m)

    • 我们使用了 std::vector<std::pair<int, int>> 来存储 AA 和 BB 的值和下标，占用了 O(n+m)O(n+m) 的空间。
    • 两个 bitset 各自需要 O(n/w)O(n/w) 的空间。
    • 所以总的空间复杂度是 O(n+m)O(n+m)。

知识点总结 ​

这道题真是一次有趣的冒险呢，喵！我们用到了好几个强大的工具：

  1. 问题转化: 把一个复杂的多重条件匹配问题，转化为多个简单条件的交集问题。这是解决复杂问题时一个非常重要的思路哦！
  2. bitset: bitset 是进行大规模位运算的神器！它能把很多独立的布尔判断并行化处理，特别适合解决这类带有“所有/任意”量词的匹配或约束问题。
  3. 排序与双指针: 当处理与大小关系相关的约束时，排序是一个非常自然的想法。而双指针则是在两个或多个有序序列上高效移动的经典技巧，它避免了重复的扫描，大大降低了时间复杂度。
  4. 卷积思想: 虽然我们没有直接用FFT/NTT，但bitset的移位和相与操作，本质上是在做一种布尔域上的卷积。ans &= (P >> j) 这个操作，就是在计算一个模式（由BjB_j定义）在主串（由AA定义）上的所有匹配位置。理解这一点，以后遇到类似的模式匹配问题，就能更快地想到 bitset 这个工具啦！

希望这篇题解能帮到你，如果还有问题，随时可以再来找我玩哦，喵~