题意

给出一些数，每次询问某一区间有多少数不超过 \(x\) 。

分析

题目本身没什么好说，这道题有多种解法。

1. 主席树模板题
2. 树状数组

树状数组的解法还是蛮有启发性的，首先如果数据不大，我们可以用二维树状数组去做，将每个数的大小看做第二维。但可惜，数据很大，这样显然会爆掉内存。可以换个思路，我们真的需要第二维吗，有没有什么办法去掉第二维呢，答案是肯定的，考虑将查询按数的大小排序，当遍历到一个查询时，树状数组中更新所有不超过这个数的大小的位置的值（将对应的位置加 1 ），此时再去查询，直接就是某个区间的和，因为我们查询的数是按从小到大排序的，所有到后面的查询，前面的数仍然满足条件。

code

#include
    
     typedef long long ll;using namespace std;const int MAXN = 1e5 + 10;struct AA {    int h, i;    bool operator < (const AA& o) const {        return h < o.h;    }}a[MAXN];struct BB {    int l, r, h, i;    bool operator < (const BB& o) const {        return h < o.h;    }}b[MAXN];int ans[MAXN], f[MAXN];void update(int x) {    while(x < MAXN) {        f[x]++;        x += x & -x;    }}int query(int x) {    int res = 0;    while(x) {        res += f[x];        x -= x & -x;    }    return res;}int main() {    int T, kase = 1;    scanf("%d", &T);    while(T--) {        int n, m;        memset(f, 0, sizeof f);        scanf("%d%d", &n, &m);        for(int i = 0; i < n; i++) {            scanf("%d", &a[i].h);            a[i].i = i;        }        for(int i = 0; i < m; i++) {            scanf("%d%d%d", &b[i].l, &b[i].r, &b[i].h);            b[i].i = i;        }        sort(a, a + n);        sort(b, b + m);        for(int i = 0, j = 0; i < m; i++) {            while(j < n && a[j].h <= b[i].h) {                update(a[j].i + 1);                j++;            }            ans[b[i].i] = query(b[i].r + 1) - query(b[i].l);        }        printf("Case %d:\n", kase++);        for(int i = 0; i < m; i++) printf("%d\n", ans[i]);    }    return 0;}