hdu 4417 2012杭州网络赛

给出 n 个数，m个询问，对于每个询问输出[l,r]区间里面大于 h 的数个数，由于n和m都很大，直接搞肯定不行，可以用线段树求解。
线段树每个区间保存与该区间长度一样对应的数据段，然后进行排序，查询的时候如果该区间包含在要询问的区间，那么直接二分查上界即可，否则继续向下询问。。
[cpp]
#include<iostream>
#include<algorithm>
using namespace std;

#define lson u<<1
#define rson u<<1|1
#define MAXN 100010

int dat[MAXN];

struct Node{
    int lef,rig;
    //int sum;
    int *sub;

}T[MAXN<<2];

void Build(int u,int l,int r){
    T[u].lef=l;
    T[u].rig=r;
    T[u].sub=new int[r-l+3];
    int subc=0;
    for(int i=l;i<=r;i++)T[u].sub[subc++]=dat[i];
    sort(T[u].sub,T[u].sub+subc);
    if(l==r)return;
    int mid=(l+r)>>1;
    Build(lson,l,mid);
    Build(rson,mid+1,r);
}

void finalizer(int u,int l,int r){
    delete[] T[u].sub;
    if(l==r)return;
    int mid=(l+r)>>1;
    finalizer(lson,l,mid);
    finalizer(rson,mid+1,r);
}

int Query(int u,int l,int r,int h){
    if(l<=T[u].lef&&T[u].rig<=r){
        int cnt=upper_bound(T[u].sub,T[u].sub+r-l+1,h)-T[u].sub;
        return cnt;
    }
    else{
        if(r<=T[lson].rig)return Query(lson,l,r,h);
        if(l>=T[rson].lef)return Query(rson,l,r,h);
        else return Query(lson,l,T[lson].rig,h)+Query(rson,T[rson].lef,r,h);
    }
}

int main(){
    int t,n,q;
    scanf("%d",&t);
    for(int cas=1;cas<=t;cas++){

        scanf("%d%d",&n,&q);
        for(int i=1;i<=n;i++)scanf("%d",dat+i);

        printf("Case %d:\n",cas);
        Build(1,1,n);
        int lf,rg,hg;
        while(q--){
            scanf("%d%d%d",&lf,&rg,&hg);
            printf("%d\n",Query(1,lf+1,rg+1,hg));
        }
        finalizer(1,1,n);
    }
}

补充：软件开发 , C++ ,