HDU 4417 Super Mario（莫队 + 树状数组 + 离散化）

Super Mario

思路

区间查找问题，容易想到离线莫队，确实这题就是莫队，接下来我们考虑如何维护区间高度值问题。

既然是离线嘛，我们容易想到离散化和他挂钩，想想这题是否需要离散化，高度的最大值是$100000000$，但是我们的数据最大值只有$100000$，由此我们可以考虑离散化之后用树状数组来维护区间的高度值，再通过树状数组的前缀和查询来得到我们需要的$[1,h]$的答案，由此一个完美的算法(莫队 + 离散化 + 树状数组)就呈现出来了。

具体细节我在代码中详细讲述。

代码

/*
  Author : lifehappy
*/
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>


#define mp make_pair
#define pb push_back
#define endl '\n'

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

const double pi = acos(-1.0);
const double eps = 1e-7;
const int inf = 0x3f3f3f3f;

inline ll read() {
    ll f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-')    f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return f * x;
}

void print(ll x) {
    if(x < 10) {
        putchar(x + 48);
        return ;
    }
    print(x / 10);
    putchar(x % 10 + 48);
}

const int N = 1e5 + 10;

int h[N], a[N], tree[N], pos[N], ans[N], n, m, block, tot;

struct Node {
    int l, r, h, id;
    bool operator < (const Node & t) const {
        return (l / block) != (t.l / block) ? l < t.l : ((l / block) & 1) ? r < t.r : r > t.r;
    }
}ask[N];

void update(int x, int value) {
    while(x <= tot) {
        tree[x] += value;
        x += (-x) & (x);
    }
}

int query(int x) {
    int ans = 0;
    while(x) {
        ans += tree[x];
        x -= (-x) & (x);
    }
    return ans;
}

void add(int pos) {
    update(pos, 1);
}

void del(int pos) {
    update(pos, -1);
}

int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int _ = read();
    for(int cas = 1; cas <= _; cas++) {
        printf("Case %d:\n", cas);
        n = read(), m = read(), block = sqrt(n);
        for(int i = 1; i <= n; i++) h[i] = a[i] = read();
        sort(a + 1, a + 1 + n);
        tot = unique(a + 1, a + n + 1) - (a + 1);//对高度进行离散化操作，这点应该没问题。
        for(int i = 1; i <= m; i++) {
            ask[i] = {(int)read() + 1, (int)read() + 1, (int)read(), i};//为了顺手，我把所有的坐标向右移动了一格。
        }
        sort(ask + 1, ask + 1 + m);//为了莫队，进行排序。
        int l = 1, r = 0;
        for(int i = 1; i <= n; i++) {//把每一个位置离散化后的位置记录下来，方便后面查询。
            pos[i] = lower_bound(a + 1, a + tot + 1, h[i]) - a;
        }
        for(int i = 1; i <= m; i++) {//莫队开始了。
            while(r < ask[i].r) add(pos[++r]);
            while(r > ask[i].r) del(pos[r--]);
            while(l > ask[i].l) add(pos[--l]);
            while(l < ask[i].l) del(pos[l++]);
            //查询的是小于等于当前高度的数量，所以直接upper_bound - 1操作即可。
            ans[ask[i].id] = query(upper_bound(a + 1, a + tot + 1, ask[i].h) - a - 1);
        }
        for(int i = 1; i <= m; i++) printf("%d\n", ans[i]);
        for(int i = 1; i <= tot; i++) tree[i] = 0;//树状数组清零。
    }
	return 0;
}

本文地址：https://blog.csdn.net/weixin_45483201/article/details/107573887