HDOJ 3333 Turing Tree 線段樹 單點更新 成段查詢

[cpp]
//HDOJ 3333 Turing Tree 線段樹 單點更新 成段查詢 
 
/*
題意：求某區間沒所有值不同的數的總和
 
思路：先對所有的詢問按照區間末尾排序
      然後從序列前面開始遍歷，當遇到相同的元素的時候
      將前面的元素刪除，這樣保證有重復的元素一定出現在距離區間末尾最近的
      轉化後就變成簡單的單點更新 區間求和了
      數據較大 要離散化處理
 
*/ 
 
#include<stdio.h> 
#include<string.h> 
#include<stdlib.h> 
 
#define N 30005 
#define M 100005 
#define lson rt<<1,l,mid 
#define rson rt<<1|1,mid+1,r 
 
int T,n,m,cnt; 
__int64 sum[N<<2],ans[M]; 
int num[N],s[N],vis[N]; 
 
struct node{ 
    int from; 
    int to; 
    int id; 
}q[M]; 
 
int cmp(const void *a,const void *b){ 
    return *(int *)a - *(int *)b; 
}  www.2cto.com
 
int cmp1(const void *a,const void *b){ 
    return (*(node *)a).to - (*(node *)b).to; 
} 
 
void Pushup(int rt){ 
    sum[rt] = sum[rt<<1] + sum[rt<<1|1]; 
} 
 
void Build(int rt,int l,int r){ 
    if(l == r){ 
        scanf("%d",&num[cnt]); 
        s[cnt] = num[cnt]; 
        sum[rt] = num[cnt++]; 
        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 = (l + r) >> 1; 
    if(x <= mid) Update(lson,x,c); 
    else            Update(rson,x,c); 
    Pushup(rt); 
} 
 
__int64 Query(int rt,int l,int r,int L,int R){ 
    if(L <= l && R >= r) 
        return sum[rt]; 
    int mid = (r + l) >> 1; 
    __int64 res = 0; 
    if(L <= mid) res += Query(lson,L,R); 
    if(R > mid ) res += Query(rson,L,R); 
    return res; 
} 
 
void Debug(int n){ 
    int i; 
    for(i = 1; i <= n; ++i) 
        printf("sum[%d] %I64d\n",i,sum[i]); 
} 
 
int Bin(int key){ 
    int l=0,r = cnt,mid; 
    while(r >= l){ 
        mid = (l + r) >> 1; 
        if(s[mid] == key) return mid; 
        if(s[mid] < key) l = mid + 1; 
        else r = mid - 1; 
    } 
    return -1; 
} 
 
void Init(){ 
    int i; 
    cnt = 0; 
    scanf("%d",&n); 
    Build(1,1,n); 
    //Debug(10); 
    qsort(s,n,sizeof(s[0]),cmp); 
    for(i = cnt = 1; i < n; ++i) 
        if(s[i]!= s[i-1]) 
            s[cnt++] = s[i]; 
    --cnt; 
    scanf("%d",&m); 
    for(i = 0; i < m; ++i){ 
        scanf("%d %d",&q[i].from,&q[i].to); 
        q[i].id = i; 
    } 
    qsort(q,m,sizeof(q[0]),cmp1); 
} 
 
void Solve(){ 
    int i,j,cur; 
    j = 0; 
    memset(vis,-1,sizeof(vis)); 
    for(i = 0; i < n; ++i){ 
        cur = Bin(num[i]); 
        if(vis[cur] == -1) 
            vis[cur] = i+1; 
        else{ 
            Update(1,1,n,vis[cur],-num[i]); 
            vis[cur] = i+1; 
        } 
        for(;j < m; ++j){ 
            if(q[j].to == i+1){ 
                ans[q[j].id] = Query(1,1,n,q[j].from,q[j].to); 
            } 
            else 
                break; 
        } 
    } 
} 
 
void Print(){ 
    int i; 
    for(i = 0; i < m; ++i) 
        printf("%I64d\n",ans[i]); 
} 
 
int main(){ 
    scanf("%d",&T); 
    while(T--){ 
        Init(); 
        Solve(); 
        Print(); 
    } 
    return 0; 
}