hdoj-4417(做法二 树状数组离线解法，对所有的查询先保存进行排序后有序的查询） 好腻害！

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;;
const int N=1e5+7;
struct T {
    int key;
    int id;
};
struct ask {
    int lr;
    int hr;
    int val;
    int id;
};
T  arr[N];
ask q[N];
int tree[N];
int ans [N];
int n,m;
bool cmp1 (T a,T b) {
    return a.key<b.key;
}
bool cmp2 (ask a,ask b) {
    return a.val<b.val;
}
void add (int x,int k) {
    while (k<=n) {
        tree[k]+=x;
        k+=k&(-k);
    }
}
int sum (int k) {
    int _ans=0;
    while (k) {
        _ans+=tree[k];
        k-=k&(-k);
    }
    return _ans;
}
int main ()
{
    int T;
    scanf ("%d",&T);
    int num=1;
    while (T--) {
        printf("Case %d:
",num++);
        scanf ("%d %d",&n,&m);
        for (int i=1;i<=n;i++) {
            scanf ("%d",&arr[i].key);
            arr[i].id=i;
        }
        sort (arr+1,arr+1+n,cmp1);
        for (int i=1;i<=m;i++) {
            scanf ("%d %d %d",&q[i].lr,&q[i].hr,&q[i].val);
            q[i].id=i;
        }
        sort (q+1,q+1+m,cmp2);
        memset (tree,0,sizeof(tree));
        int top=1;
        for (int i=1;i<=m;i++) {
            while (top<=n&&arr[top].key<=q[i].val)   {
                add(1,arr[top].id);
                top++;
            }
            ans[q[i].id]=sum(q[i].hr+1)-sum(q[i].lr);
        }
        for (int i=1;i<=m;i++)
            printf("%d
",ans[i]);
    }
    return 0;
}