Turing Tree

Time Limit: 6000/3000 MS (Java/Others)
Memory Limit: 32768/32768 K (Java/Others)

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

• 离线化
• 从左到右处理原数列
• 对询问排序

不再是难题。

/* 
 * File:   main.cpp
 * Author: semprathlon
 *
 * Created on March 25, 2016, 4:02 PM
 */
#include 
#include 
#include 
#include 
#include 

这是一场炼狱般的较量。无心游玩，艰苦奋斗。

编写适应多变需求的二分查找代码。

ZYB’s Biology

平淡无奇的匹配

ZYB’s Game

惊异于“最优策略”的选取，最终结果竟与奇偶性挂钩。

ZYB’s Premutation

常规题型，旧题重演，竟然跑偏了。
半年多前的某基础题的逆向问题。
同样用线段树或树状数组解决，关键是实现查找第k大的数、删除第k大的数并维护。也有基于查询数的更抽象高效的解法。
树状数组：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

/**
 * Dec 5, 2015 8:39:53 PM
 * PrjName: 1205-03-2
 * @semprathlon
 */
import java.io.*;
import java.util.*;
public class Main {
    static int[] a,f;
    static BIT tr;
    static HashSet<Integer> st=new HashSet<Integer>();
    static void print(int[] a,PrintWriter out){
        int n=a.length-1;
        for(int i=1;i<=n;i++)
            out.print(a[i]+(i<n?" ":""));
        out.println();
    }
    public static void main(String[] args) throws IOException{
        InputReader in=new InputReader(System.in);
        PrintWriter out=new PrintWriter(System.out);
        int T=in.nextInt();
//        tr=new BIT(5);
//        out.print(tr.lowbit(2));
        while(T-->0){
            int n=in.nextInt();
            a=new int[n+1];
            f=new int[n+1];
            tr=new BIT(n);
            for(int i=1;i<=n;i++){
                f[i]=in.nextInt();
                tr.add(i, 1);
            }
            
            for(int i=n;i>=1;i--){
                f[i]-=f[i-1];
                int tmp=tr.find(i-f[i]-1);
//                out.println(i+","+f[i]+","+tmp);
                a[i]=tmp;
                tr.add(tmp, -1);
            }
            print(a, out);
        }
        out.flush();
        out.close();
    }
}
class BIT{
    int[] data;
    int sz;
    BIT(){}
    BIT(int _sz){
        sz=_sz;
        data=new int[sz+1];
    }
    int lowbit(int x){
        return x&(-x);
    }
    void add(int p,int v){
        while(p<=sz){
            data[p]+=v;
            p+=lowbit(p);
        }
    }
    int sum(int p){
        int res=0;
        while(p>0){
            res+=data[p];
            p-=lowbit(p);
        }
        return res;
    }
    int find(int p){
        int l=1,r=sz;
        while(l<r){
            int mid=(l+r)>>1;
            if (sum(mid)<=p)
                l=mid+1;
            else
                r=mid;
        }
        
        return l;
    }
}

线段树：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

/**
 * Dec 6, 2015 4:42:31 PM
 * PrjName: 1205-03-3
 * @semprathlon
 */
import java.io.*;
import java.util.*;
public class Main {
    static int[] a,f;
    static ST tr;
    static HashSet<Integer> st=new HashSet<Integer>();
    static void print(int[] a,PrintWriter out){
        int n=a.length-1;
        for(int i=1;i<=n;i++)
            out.print(a[i]+(i<n?" ":""));
        out.println();
    }
    public static void main(String[] args) throws IOException{
        InputReader in=new InputReader(System.in);
        PrintWriter out=new PrintWriter(System.out);
        int T=in.nextInt();
        while(T-->0){
            int n=in.nextInt();
            a=new int[n+1];
            f=new int[n+1];
            tr=new ST(n);
            tr.build(1, 1, n);
            for(int i=1;i<=n;i++)
                f[i]=in.nextInt();
            
            for(int i=n;i>=1;i--){
                f[i]-=f[i-1];
                int tmp=tr.query(1, 1, n, f[i]+1);
//                out.println(i+","+f[i]+","+tmp);
                a[i]=tmp;
                
            }
            print(a, out);
        }
        out.flush();
        out.close();
    }
}
class ST{
    int[] l,r,m,v;
    int sz;
    ST(){}
    ST(int _sz){
        sz=_sz<<2;
        l=new int[sz];
        r=new int[sz];
        m=new int[sz];
        v=new int[sz];
    }
    void build(int k,int x,int y){
        l[k]=x;r[k]=y;m[k]=(x+y)>>1;
        if (x<y){
            build(k<<1,x,m[k]);
            build(k<<1|1,m[k]+1,y);
        }
        v[k]=y-x+1;
    }
    int query(int k,int x,int y,int q){
        if (l[k]==r[k]){
            v[k]=0;
            return l[k];
        }
        int res=0;
        if (v[k<<1|1]>=q)
            res=query(k<<1|1, m[k]+1, y, q);
        else
            res=query(k<<1,x,m[k],q-v[k<<1|1]);
        v[k]=v[k<<1]+v[k<<1|1];
        return res;
    }
    
}