现在的位置: 首页 > 综合 > 正文

【HDU】3333 Turing Tree 线段树

2017年11月20日 ⁄ 综合 ⁄ 共 3188字 ⁄ 字号 评论关闭

Turing Tree

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

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

传送门:【HDU】3333 Turing Tree

题目大意:给你一串长度为n(n <= 30000)的序列,编号从1开始,序列中每个元素最大不超过10^9。
接下来Q组询问,每组是一个区间,要你回答这个区间中不相同的数之和为多少。

题目分析:
这题比较巧妙的思路就是,先把所有信息保存下来,离线处理,将区间按照右端点从小到大排序,然后从1到n依次向线段树中作单点插入,插入前先判断一下之前这个元素是否已经插入过一次,是的话,将之前位置上的该元素置零,然后再插入该元素。如果插入位置上被区间右端点覆盖,则为该区间求一次区间和,答案就是该区间要求的满足题意的解。
当然区间没必要排序,直接前向星保存即可。而且元素过大需要离散化。
为什么这样是可行的?稍微想想就可以知道是对的。

代码如下:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;

typedef long long Int ;

#define ls ( o << 1 )
#define rs ( o << 1 | 1 )
#define rt l , r , o
#define root 1 , n , 1
#define lson l , m , ls
#define rson m + 1 , r , rs
#define clear( A , X ) memset ( A , X , sizeof A )
#define mid ( ( l + r ) >> 1 )
#define max( A , B ) ( ( A ) > ( B ) ? ( A ) : ( B ) )
#define min( A , B ) ( ( A ) < ( B ) ? ( A ) : ( B ) )

const int maxN = 100005 ;

struct Edge {
    int i , v , n ;
} ;

int a[maxN] , b[maxN] ;
Edge edge[maxN] ;
int adj[maxN] , cntE ;
Int sum[maxN << 2] , res[maxN] ;
int flag[maxN] ;

void addedge ( int i , int u , int v ) {
    edge[cntE].i = i ; edge[cntE].v = v ; edge[cntE].n = adj[u] ; adj[u] = cntE ++ ;
}

void PushUp ( int o ) {
    sum[o] = sum[ls] + sum[rs] ;
}

void Update ( int pos , int val , int l , int r , int o ) {
    if ( l == r ) {
        sum[o] = val ;
        return ;
    }
    int m = mid ;
    if ( pos <= m ) Update ( pos , val , lson ) ;
    else Update ( pos , val , rson ) ;
    PushUp ( o ) ;
}

Int Query ( int L , int R , int l , int r , int o ) {
    if ( L <= l && r <= R ) return sum[o] ;
    int m = mid ;
    Int ans = 0 ;
    if ( L <= m ) ans += Query ( L , R , lson ) ;
    if ( m <  R ) ans += Query ( L , R , rson ) ;
    return ans ;
}

int Bin_Search ( int x , int l , int r ) {
    while ( l < r ) {
        int m = mid ;
        if ( b[m] < x ) l = m + 1 ;
        else r = m ;
    }
    return l ;
}

int Unique ( int *b , int n ) {
    int cnt = 0 ;
    sort ( b , b + n ) ;
    for ( int i = 1 ; i < n ; ++ i ) if ( b[i] != b[cnt] ) b[++ cnt] = b[i] ;
    return cnt + 1 ;
}

void work () {
    int n , m , l , r , cnt = 0 ;
    scanf ( "%d" , &n ) ;
    
    for ( int i = 1 ; i <= n ; ++ i ) {
        scanf ( "%d" , &a[i] ) ;
        b[cnt ++] = a[i] ;
    }
    
    cnt = Unique ( b , cnt ) ;
    clear ( adj , -1 ) ;
    cntE = 0 ;
    
    scanf ( "%d" , &m ) ;
    for ( int i = 1 ; i <= m ; ++ i ) {
        scanf ( "%d%d" , &l , &r ) ;
        addedge ( i , r , l ) ;
    }
    
    clear ( flag , 0 ) ;
    clear ( sum , 0 ) ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        int x = Bin_Search ( a[i] , 0 , cnt ) ;
        if ( flag[x] ) Update ( flag[x] , 0 , root ) ;
        Update ( i , a[i] , root ) ;
        flag[x] = i ;
        for ( int j = adj[r = i] ; ~j ; j = edge[j].n ) {
            l = edge[j].v ;
            res[edge[j].i] = Query ( l , r , root ) ;
        }
    }
    
    for ( int i = 1 ; i <= m ; ++ i ) {
        printf ( "%I64d\n" , res[i] ) ;
    }
}

int main () {
    int T ;
    scanf ( "%d" , &T ) ;
    while ( T -- ) work () ;
    return 0 ;
}

抱歉!评论已关闭.