Super Mario

GitHub返回列表

OJ: hdu

题目 ID: 4417

标签: 可持久化线段树线段树

日期: 2025-11-30 13:32

目录

  1. Super Mario
    1. 题目链接
    2. 题目大意
    3. 暴力代码
    4. 解题思路
      1. 1. 离线处理
      2. 2. 排序带来的好处
      3. 3. 树状数组的应用
      4. 4. 算法流程
    5. 代码实现

Super Mario

题目链接

HDU-4417 Super Mario

题目大意

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

暴力代码

cpp
#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. 树状数组的应用

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

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

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

4. 算法流程

  1. 数据结构化：

    • 将 n 个砖块存为一个结构体数组 blocks，每个元素包含 (height, position)。
    • 将 m 个查询存为一个结构体数组 queries，每个元素包含 (H, L, R, original_index)。

  2. 排序：

    • 对 blocks 数组按 height 升序排序。
    • 对 queries 数组按 H 升序排序。

  3. 处理查询：

    • 初始化一个大小为 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]。

  4. 输出：

    • 所有查询处理完毕后，按 0 到 m-1 的顺序输出 ans 数组中的结果。

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

代码实现

cpp
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+5;

int n,m;
int unique_cnt;
int a[maxn],b[maxn];
int root[maxn]; // root[i] 第i颗树的根
struct Node {
    int l,r,sum; // sum 区间内权值(数字的数量)
} tree[maxn << 5]; // 2^5 倍

int node_cnt = 0;
int get_node() {return ++node_cnt;}

// 建立线段树
void build() {

}

int update(int u,int l,int r,int id) {
    int rt = get_node();
    tree[rt] = tree[u]; // 复制原来的结点
    tree[rt].sum ++; // 多了一个值,增加1

    if( l==r) return rt; // 叶子结点,返回

    int mid = (l+r) >>1;
    if( id <= mid ) tree[rt].l = update(tree[u].l,l,mid,id);
    if( id > mid) tree[rt].r = update(tree[u].r,mid+1,r,id);
    return rt;
}

// u,v 对以两个树上对应的结点
// 本质是求区间和
int query(int u,int v,int l,int r,int k)
{
    // 结点对应的区间,完全被包含
    if( r <= k ) {
        return tree[v].sum - tree[u].sum;
    }

    if( l == r) {
        return tree[v].sum - tree[u].sum;
    }
        
    // 当前结点的左子树sum
    int mid = (l+r) >>1;
    int lsum = 0, rsum = 0;
    if( mid >= 1 ) 
        lsum = query(tree[u].l,tree[v].l,l,mid,k);
    if( mid+1 <= k)
        rsum = query(tree[u].r,tree[v].r, mid+1, r, k);

    return lsum + rsum;

}


void init() {
    std::cin >> n >> m;
    for(int i = 1;i <= n ;++i ) // i: 1->n
    {
        std::cin >> a[i];
        b[i] = a[i];
    }
    sort(b+1,b+1+n);
    unique_cnt= std::unique(b+1,b+1+n)- (b+1);// 离散化

}

int main (int argc, char *argv[]) {
    int T;
    std::cin >> T;
    int case_num = 1;
    while (T--) {
        printf("Case %d:\n", case_num++);
        node_cnt = 0;
        init();

        // 建立n颗线段树
        for(int i = 1;i <= n ;++i ) // i: 1->n
        {
            // 找到a[i] 对应的离散化后的值
            int id = lower_bound(b+1, b+1+unique_cnt, a[i]) - b;
            // cout << id << " ";
            root[i] = update(root[i-1],1,unique_cnt,id);
        }
        // cout << endl;

        while (m--) {
            int x,y,k;
            std::cin >> x >> y >> k;
            x++;y++;
            // 得到k对应的离散化后的值
            int kk = lower_bound(b+1, b+1+unique_cnt,k) - b;

            // 细节!!: 如果查询到的值就是k
            // 表明k 本身 离散化后存在
            // 如果k 不在离散化后的值,
            if( b[kk] != k ) {
                kk--;
            }
            if( kk == 0) { // 特判
                // 这里是一个细节 
                // 线段树里面的区间 [1,unique_cnt]
                // 如果要 查询 <=0,那么 就会出现错误
                printf("0\n");
            }
            else {
                int t =  query(root[x-1], root[y],1,unique_cnt,kk);
                std::cout << t << "\n";
            }
        }
    }
    
    return 0;
}