HDU 3333 Turing Tree

Turing Tree

Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4671 Accepted Submission(s): 1649

Problem Description

After inventing Turing Tree, 3xian always felt boring when solving problems about intervals, because Turing Tree could easily have the solution. As well, wily 3xian made lots of new problems about intervals. So, today, this sick thing happens again...

Now given a sequence of N numbers A1, A2, ..., AN and a number of Queries(i, j) (1≤i≤j≤N). For each Query(i, j), you are to caculate the sum of distinct values in the subsequence Ai, Ai+1, ..., Aj.

Input

The first line is an integer T (1 ≤ T ≤ 10), indecating the number of testcases below.
For each case, the input format will be like this:
* Line 1: N (1 ≤ N ≤ 30,000).
* Line 2: N integers A1, A2, ..., AN (0 ≤ Ai ≤ 1,000,000,000).
* Line 3: Q (1 ≤ Q ≤ 100,000), the number of Queries.
* Next Q lines: each line contains 2 integers i, j representing a Query (1 ≤ i ≤ j ≤ N).

Output

For each Query, print the sum of distinct values of the specified subsequence in one line.

Sample Input

2 3 1 1 4 2 1 2 2 3 5 1 1 2 1 3 3 1 5 2 4 3 5

Sample Output

1 5 6 3 6

Author

3xian@GDUT

Source

HDOJ Monthly Contest – 2010.03.06

Recommend

lcy

/*----------------------------------------------
File: F:ACM源代码数据结构--树状数组Turing_Tree.cpp
Date: 2017/5/31 17:40:20
Author: LyuCheng
----------------------------------------------*/
/*
题意：给你一个数组，然后让你统计区间内的不相同的数字的和

思路：树状数组，思想就是边更新，边查询，每次更新一个点，更新这个点的时候，如果这个点的值在前面出现过了，就删除这个值，然后在这个点更新
    顺便更新查询结果，怎么记录这个值是不是在前面出现过了呐？用一个有序的数组，每次查找的都是第一次出现的位置，用一个Last数组记录这个数、
    上一次出现的位置
*/
#include <bits/stdc++.h>
#define LL long long 
#define MAXN 30005
#define MAXNQ 100000
#define lowbit(x) x&(-x)
using namespace std;

struct Node{
    int l,r,id;
    bool operator <(const Node & other) const{
        return r<other.r;
    }
}node[MAXNQ];
int t;
int n,q;
LL a1[MAXN],a2[MAXN];//一个记录原数组，一个记录a[i]是不是在前面出现过了
LL res[MAXNQ];
LL c[MAXN];
int Last[MAXN];

void insert(int x,LL val){
    while(x<MAXN){
        c[x]+=val;
        x+=lowbit(x);
    }
    return ;
}

LL getsum(int x){
    LL s=0;
    while(x>0){
        s+=c[x];
        x-=lowbit(x);
    }
    return s;
}

void init(){
    memset(Last,0,sizeof Last);
    memset(res,0,sizeof res);
    memset(c,0,sizeof c);
}

int main()
{
    // freopen("in.txt","r",stdin);
    scanf("%d",&t);
    while(t--){
        init();
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%lld",&a1[i]);
            a2[i]=a1[i];
        }
        scanf("%d",&q);
        for(int i=1;i<=q;i++){
            scanf("%d%d",&node[i].l,&node[i].r);
            node[i].id=i;
        }
        sort(a2+1,a2+n+1);
        sort(node+1,node+q+1);
        int cur=1;
        for(int i=1;i<=n;i++){
            int pos=lower_bound(a2+1,a2+n+1,a1[i])-a2;
            if(Last[pos]==0){//如果这个数以前没出现过
                insert(i,a1[i]);
                Last[pos]=i;
            }else{//这个数以前出现过
                insert(Last[pos],-a1[i]);
                insert(i,a1[i]);
                Last[pos]=i;
            }
            while(node[cur].r==i&&cur<=q){//更新查询的值
                res[node[cur].id]=getsum(node[cur].r)-getsum(node[cur].l-1);
                cur++;
            }
        }
        
        for(int i=1;i<=q;i++){
            printf("%lld
",res[i]);
        }
    }
    return 0;
}