HDOJ 4417 Super Mario 線段樹 單點更新 成段查詢

[cpp] 
//HDOJ 4417 Super Mario 線段樹 轉化為單點更新 成段查詢 
 
/*
題意：查詢區間內小於等於某數的數的總和
 
思路：離線查詢，先記錄所有的詢問並排序，然後一邊刪一邊查，查之前把不滿足的刪掉
      就轉化為簡單的單點更新，成段求和。
*/ 
 
#include<stdio.h> 
#include<string.h> 
#include<stdlib.h> 
 
#define lson rt<<1,l,mid 
#define rson rt<<1|1,mid+1,r 
#define N 100005 
 
int T,n,m,cnt,ca = 1; 
int sum[N<<2],ans[N]; 
 
struct Node{ 
    int x; 
    int id; 
}s[N]; 
 
struct node{ 
    int from; 
    int to; 
    int k; 
    int id; 
}q[N]; 
 
int cmp(const void *a,const void *b){ 
    return (*(Node *)b).x - (*(Node *)a).x; 
} 
 
int cmp1(const void *a,const void *b){ 
    return (*(node *)b).k - (*(node *)a).k; 
} 
 
void Pushup(int rt){ 
    sum[rt] = sum[rt<<1]+sum[rt<<1|1]; 
} 
 
void Debug(int n){ 
    int i; 
    for(i = 1; i <= n; ++i) 
        printf("sum[%d] : %d\n",i,sum[i]); 
} 
 
void Build(int rt,int l,int r){ 
    if(l == r){ 
        scanf("%d",&s[cnt].x); 
        s[cnt].id = cnt++; 
        sum[rt] = 1; 
        return ; 
    } 
    int mid = (l + r) >> 1; 
    Build(lson); 
    Build(rson); 
    Pushup(rt); 
} 
 
void Update(int rt,int l,int r,int x,int c){ 
    if(l == r){ 
        sum[rt] += c; 
        return ; 
    } 
    int mid = (r + l) >> 1; 
    if(x <= mid) Update(lson,x,c); 
    else            Update(rson,x,c); 
    Pushup(rt); 
} 
 
int Query(int rt,int l,int r,int L,int R){ 
    if(L <= l && R >= r){ 
        return sum[rt]; 
    } 
    int res = 0; 
    int mid = (l + r) >> 1; 
    if(L <= mid) res += Query(lson,L,R); 
    if(R > mid ) res += Query(rson,L,R); 
    return res; 
} 
 
void Init(){ 
    int i; 
    cnt = 1; 
    scanf("%d %d",&n,&m); 
    Build(1,1,n); 
    qsort(s+1,n,sizeof(s[0]),cmp); 
    for(i = 1; i <= m; ++i){ 
        scanf("%d %d %d",&q[i].from,&q[i].to,&q[i].k); 
        q[i].id = i; 
    } 
    qsort(q+1,m,sizeof(q[0]),cmp1); 
} 
 
void Solve(){ 
    int i,j = 1; 
    memset(ans,0,sizeof(ans)); 
    for(i = 1; i <= n; ++i){ 
        while(s[i].x <= q[j].k){ 
            ans[q[j].id] = Query(1,1,n,q[j].from+1,q[j].to+1); 
            ++j; 
            if(j > m)    break; 
        } 
        if(s[i].x > q[j].k){ 
            Update(1,1,n,s[i].id,-1);    
        } 
    } 
} 
 
void Print(){ 
    int i; 
    printf("Case %d:\n",ca++); 
    for(i = 1; i <= m; ++i) 
        printf("%d\n",ans[i]); 
} 
 
int main(){ 
    scanf("%d",&T); 
    while(T--){ 
        Init(); 
        Solve(); 
        Print(); 
    } 
    return 0; 
}