求区间（L, R）小于k的数有多少个

二位数点典中点。
题目链接：数数
以前写的博客链接：
小沙的remake
那题刚好询问的是小于等于a[i]的数有多少个，所以方法二也很好做，但是这题询问的是其他的数 H[i]，所以如果用方法二的话，还得离散化，十分麻烦。
用方法一就简单多了，将数组a中小于H[i]的数的下标pos都插入树状数组中，直接查询que - que(l - 1)就是答案。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 5, mod = 1e9 + 7;
int c[N];
int n;
struct node{
    
    int val, pos;
    bool operator < (const node &k) const {
    
        if (val != k.val) return val < k.val;
        return pos < k.pos;
    }
} a[N];
struct kk{
    
    int l, r, val, pos;
    bool operator < (const kk &k) const{
    
        return val < k.val;
    }
} d[N];
int ans[N];
void add(int i, int x)
{
    
    while(i <= n){
    
        c[i] += x;
        i += (i & -i);
    }
}
int que(int i)
{
    
    int ret = 0;
    while(i){
    
        ret += c[i];
        i -= (i & -i);
    }
    return ret;
}
signed main() 
{
    
    int tt;
    cin >> tt;
    while(tt--){
    
        int q;
        scanf("%lld%lld", &n, &q);
        for (int i = 1; i <= n; i++) {
    
            scanf("%lld", &a[i].val);
            a[i].pos = i;
        }
        for (int i = 1; i <= q; i++){
    
            scanf("%lld%lld%lld", &d[i].l, &d[i].r, &d[i].val);
            d[i].pos = i;
        }
        sort(a + 1, a + 1 + n);
        sort(d + 1, d + 1 + q);
        int k = 1;
        for (int i = 1; i <= q; i++){
    
            while (a[k].val <= d[i].val && k <= n){
    
                add(a[k].pos, 1);
                k++;
            }
            ans[d[i].pos] = que(d[i].r) - que(d[i].l - 1);
        }
        for (int i = 1; i <= q; i++) printf("%lld ", ans[i]);
        puts("");
        for (int i = 1; i <= n; i++) {
    
            a[i].val = a[i].pos = d[i].val = 0;
            c[i] = 0;
        }
    }
    return 0;
}