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); 
    } 
}