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.zzzyk.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;
}

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

HDOJ 3333 Turing Tree 线段树 单点更新 成段查询

HDOJ 3333 Turing Tree 线段树单点更新成段查询