询问离线处理模板题

思路：
所有询问按照k从小到大排序，为什么要这样呢？
显然，如果小与等于k1的答案处理出来了，那么怎么处理k2（k2>=k1）的答案呢？
如果在数组中所有小于等于k1的位置被高亮了，那么在数组中所有小于等于k2的高亮位置一定包含k1的
高亮位置，这样从小到大跑过去，最多高亮n个点。那么答案是什么呢？

怎么维护高亮点数呢？
直接用树状数组动态维护。
复杂度O（nlogn）

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
struct Query{
    int l, r, k;
    int id;
}q[maxn];
struct node{
    int val; int pos;
}a[maxn];
int n, m;
int ans[maxn], sum[maxn];
int lowbit(int x){
    return x & -x;
}
void add(int i, int tmp){
    while(i <= n){
        sum[i] += tmp;
        i += lowbit(i);
    }
}
int getsum(int i){
    int ans = 0;
    while(i){
        ans += sum[i];
        i -= lowbit(i);
    }
    return ans;
}
bool cmp(Query a, Query b){
    if(a.k == b.k) return a.id < b.id;
    return a.k < b.k;
}
bool cmp1(node a, node b){
    if(a.val == b.val) return a.pos < b.pos;
    return a.val < b.val;
}
int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++){
        scanf("%d", &a[i].val); a[i].pos = i;
    }
    sort(a + 1, a + n + 1, cmp1);
    int l, r, k;
    for(int i = 1; i <= m; i++){
        scanf("%d%d%d", &l, &r, &k);
        q[i].l = l; q[i].r = r; q[i].k = k; q[i].id = i;
    }
    sort(q + 1, q + m + 1, cmp);
    int j = 1;
    for(int i = 1; i <= m; i++){
        int k = q[i].k;
        for(; j <= n && a[j].val <= k; j++){
            add(a[j].pos, 1);
        }
        ans[q[i].id] = getsum(q[i].r) - getsum(q[i].l - 1);
    }
    for(int i = 1; i <= m; i++){
        printf("%d\n", ans[i]);
    }
    return 0;
}