解题思路

题目要求查询区间内小于等于 H 的数的个数。很显然的主席树，建树之后直接在目标区间的主席树内将 H 作为挡板递归计数即可。

另外此题还可以用离线树状数组求解。

参考代码

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 100001;

struct node {
    int sum, l, r;
} hjt[MAXN*40];

int a[MAXN], sorted[MAXN], num;
int root[MAXN], cnt;

int GetIdx(int v) {
    return lower_bound(sorted+1, sorted+1+num, v) - sorted;
}

void Init() {
    cnt = 0;
}

inline int CreateNode(int sum, int l, int r) {
    int idx = ++cnt;
    hjt[idx].sum = sum;
    hjt[idx].l = l;
    hjt[idx].r = r;

    return idx;
}

void Insert(int &root, int pre_rt, int pos, int l, int r) {
    root = CreateNode(hjt[pre_rt].sum+1, hjt[pre_rt].l, hjt[pre_rt].r);
    if(l == r) return;
    int m = (l+r) >> 1;
    if(pos <= m)
        Insert(hjt[root].l, hjt[pre_rt].l, pos, l, m);
    else Insert(hjt[root].r, hjt[pre_rt].r, pos, m+1, r);
}

int Query(int s, int e, int h, int l, int r) {
    if(r <= h) return hjt[e].sum - hjt[s].sum;
    int m = (l+r) >> 1;
    if(h <= m)
        return Query(hjt[s].l, hjt[e].l, h, l, m);
    else return hjt[hjt[e].l].sum - hjt[hjt[s].l].sum + Query(hjt[s].r, hjt[e].r, h, m+1, r);
}

int main(int argc, char const *argv[]) {
    int t, n, m, l, r, h;
    scanf("%d", &t);
    for(int cs=1; cs<=t; ++cs) {
        scanf("%d %d", &n, &m);
        Init();
        for(int i=1; i<=n; ++i) {
            scanf("%d", &a[i]);
            sorted[i] = a[i];
        }
        sort(sorted+1, sorted+1+n);
        num = unique(sorted+1, sorted+1+n) - (sorted+1);
        for(int i=1; i<=n; ++i) {
            Insert(root[i], root[i-1], GetIdx(a[i]), 1, num);
        }
        printf("Case %d:\n", cs);
        while(m--) {
            scanf("%d %d %d", &l, &r, &h);
            l++;
            r++;
            h = upper_bound(sorted+1, sorted+1+num, h) - sorted;
            if(h == 1) printf("0\n");
            else printf("%d\n", Query(root[l-1], root[r], h-1, 1, num));
        }
    }
    
    return 0;
}