我的算法书 - Super Mario

Super Mario

题目链接

题目大意

给定一个长度为 n 的序列，代表每个位置的砖块高度。有 m 次询问，每次询问一个区间 [L, R] 和一个最大跳跃高度 H，要求回答在 [L, R] 这个区间内，有多少砖块的高度小于或等于 H。

暴力代码

cpp

copy

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

        #include <iostream>
#include <vector>
#include <cstdio>

using namespace std;

void solve(int caseNum) {
    int n, m;
    // 读取 n (道路长度) 和 m (查询次数)
    if (!(cin >> n >> m)) return;

    vector<int> h(n);
    // 读取每个砖块的高度
    for (int i = 0; i < n; ++i) {
        cin >> h[i];
    }

    printf("Case %d:\n", caseNum);

    // 处理 m 次查询
    for (int i = 0; i < m; ++i) {
        int L, R, H;
        cin >> L >> R >> H;

        int count = 0;
        // 暴力核心：直接遍历 L 到 R 区间
        // 题目保证 0 <= L <= R < n，所以不需要做边界检查
        for (int j = L; j <= R; ++j) {
            if (h[j] <= H) {
                count++;
            }
        }
        printf("%d\n", count);
    }
}

int main() {
    int t;
    cin >> t;
    for (int i = 1; i <= t; ++i) {
        solve(i);
    }
    return 0;
}

解题思路

这是一个典型的二维数点问题，查询涉及位置和数值两个维度。对于这类问题，如果可以离线处理，一个常见的优化技巧是将查询排序，从而将二维问题降为一维问题。

1. 离线处理

我们可以将所有查询读入并存储起来，而不是立即回答。然后，我们按照查询的高度 H 进行升序排序。同时，我们也把所有的砖块按照高度进行升序排序。

2. 排序带来的好处

当我们按高度 H 从小到大的顺序处理查询时，我们会发现一个关键特性：对于一个查询 q_i，所有满足其高度限制 H_i 的砖块，对于后续任何查询 q_j (因为 H_j >= H_i) 也同样满足。

这意味着，我们可以维护一个数据结构，随着我们处理的查询 H 越来越大，我们将越来越多满足高度条件的砖块加入到这个数据结构中。

3. 树状数组的应用

我们需要一个数据结构，它能够：

在某个位置 pos 添加一个元素。
查询区间 [L, R] 中元素的个数。

树状数组 (Fenwick Tree) 非常适合这个任务。我们可以用一个大小为 n 的树状数组来维护砖块的位置。

4. 算法流程

数据结构化：
- 将 n 个砖块存为一个结构体数组 blocks，每个元素包含 (height, position)。
- 将 m 个查询存为一个结构体数组 queries，每个元素包含 (H, L, R, original_index)。
排序：
- 对 blocks 数组按 height 升序排序。
- 对 queries 数组按 H 升序排序。
处理查询：
- 初始化一个大小为 n 的树状数组 bit，所有元素为0。
- 初始化一个 block_ptr = 0，用于指向 blocks 数组。
- 遍历排序后的 queries 数组：
  - 对于当前查询 q，其高度为 H。我们先将所有高度小于等于 H 的砖块加入树状数组。具体操作是：while (block_ptr < n && blocks[block_ptr].height <= H)，执行 bit.add(blocks[block_ptr].position, 1)，然后 block_ptr++。
  - 此时，树状数组中值为1的位置，就代表了所有高度 ≤ H 的砖块。
  - 查询 [L, R] 区间内的砖块数，即为 bit.query(R) - bit.query(L-1)。
  - 将结果存入 ans[q.original_index]。
输出：
- 所有查询处理完毕后，按 0 到 m-1 的顺序输出 ans 数组中的结果。

通过这种方式，每个砖块和每个查询都只被处理常数次，树状数组的单次操作复杂度为 O(log n)，排序的复杂度为 O(n log n + m log m)。因此，算法总的时间复杂度为 O(n log n + m log m)，足以通过本题。

代码实现

cpp