[原创]SPOJ DQUERY - D-query [树状数组+离线 || 主席树 ]【数据结构】

2017-03-11 14:18:35 Tabris_ 阅读数：312

博客爬取于2020-06-14 22:41:21
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/61416622

题目连接:http://www.spoj.com/problems/DQUERY/

——————————————————————————————————————————
DQUERY - D-query
#sorting #tree
English Vietnamese
Given a sequence of n numbers a1, a2, …, an and a number of d-queries. A d-query is a pair (i, j) (1 ≤ i ≤ j ≤ n). For each d-query (i, j), you have to return the number of distinct elements in the subsequence ai, ai+1, …, aj.

Input

Line 1: n (1 ≤ n ≤ 30000).
Line 2: n numbers a1, a2, …, an (1 ≤ ai ≤ 106).
Line 3: q (1 ≤ q ≤ 200000), the number of d-queries.
In the next q lines, each line contains 2 numbers i, j representing a d-query (1 ≤ i ≤ j ≤ n).
Output

For each d-query (i, j), print the number of distinct elements in the subsequence ai, ai+1, …, aj in a single line.
Example

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

Output
3
2
3
——————————————————————————————————————————
题目大意：
就是给你一个序列 ，和q次询问，
询问[l,r][l,r]区间不同元素的个数

解题思路：
本来是做的主席树专题 ，然而主席树怎么做 还不会，

于是就用离线树状数组的做法水了一发

主要就是对询问的r值 排序。
然后遍历一遍序列，
每次对在树状数组上更新aia_i最后一次出现的位置,如果已经出现了 就将之前出现过的删掉就好了

每次维护查询 就是计算[l,r][l,r]区间标记的个数

============== 主席树的做法 Update===================

仔细想了想主席树的做法，
其实思路上和离线的树状数组并没有什么区别，
但是因为主席树的特性，我们可以维护一颗颗树，所以能拿到线上解决这个问题

在一颗颗树进行更新的时候,当这个值出现过,我们就将之前的删去,然后在更新,就好了

对树的维护和线段树基本相同,不赘述了

但是在处理的时候发现一个问题

1
2
3
4
5
6
7
int tem;
for(int i=1;i<=n;i++){
    tem=rt[i-1];
    if(vis[a[i]])update(tem,1,n,rt[i-1],vis[a[i]],-1);
    update(rt[i],1,n,tem,i,1);
    vis[a[i]]=i;
}

上面的能AC 而下面的却不能

1
2
3
4
5
for(int i=1;i<=n;i++){
    if(vis[a[i]])update(rt[i],1,n,rt[i-1],vis[a[i]],-1);
    update(rt[i],1,n,rt[i],i,1);
    vis[a[i]]=i;
}

最后也没弄明白怎么回事

附本题代码
——————————————————————————————————————————

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
/***
树状数组离线
*/
int n,Q;
int a[30007],vis[1000007];
struct node{
    int l, r,id;
}q[200007];
int ans[200007];

bool cmp(node A,node B){
    if(A.r==B.r) return A.l<B.l;
    return A.r<B.r;
}

int sum[1000007];
# define lowbit(x) (x&-x)
void update(int i,int v){for(;i<=n;i+=lowbit(i))sum[i]+=v;}
int getSum(int i){int ans=0;for(;i;i-=lowbit(i))ans+=sum[i];return ans;}

int main(){

    scanf("%d",&n);
    for(int i=1;i<=n;i++)   scanf("%d",&a[i]);

    scanf("%d",&Q);
    for(int i=1;i<=Q;i++)   scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;

    sort(q+1,q+1+Q,cmp);

    for(int i=1,j=1;i<=n&&j<=Q;i++){
        if(vis[a[i]]) update(vis[a[i]],-1);
        vis[a[i]]=i;  update(i,1);
        while(j<=Q&&q[j].r<=i){
            ans[q[j].id]=getSum(q[j].r)-getSum(q[j].l-1);
            j++;
        }
    }

    for(int i=1;i<=Q;i++)printf("%d\n",ans[i]);
    return 0;
}

/**
主席树
*/
# pragma comment(linker, "/STACK:1024000000,1024000000")
# include<bits/stdc++.h>

using namespace std;

typedef long long int LL;

const int    INF = (~(1<<31));
const int    N   = 30000+7;
const double eps = 1e-7;

inline int read(){
    int x=0,f=1;char ch = getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while('0'<=ch&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*f;
}
/****************************************************/

int ls[N*20],rs[N*20],sum[N*20],rt[N],tot,vis[N];
int n,q,ql,qr,x,a[N],b[N];
void build(int &rt,int l,int r){
    rt=++tot;
    sum[rt]=0;
    if(l==r) return ;
    int m = (r+l)>>1;
    build(ls[rt],l,m);
    build(rs[rt],m+1,r);
}

void update(int &rt,int l,int r,int last,int pos,int v){
    rt = ++tot;
    ls[rt] =ls[last];
    rs[rt] =rs[last];
    sum[rt]=sum[last]+v;
    if(l==r) return ;
    int m = (r+l)>>1;
    if(pos<=m) update(ls[rt],l  ,m,ls[last],pos,v);
    else       update(rs[rt],m+1,r,rs[last],pos,v);
}

int query(int ss,int tt,int l,int r,int L,int R){
    if(L<=l&&r<=R) return sum[tt]-sum[ss];
    int m = (l+r)>>1;
    int ans = 0;
    if(L<=m)  ans+=query(ls[ss],ls[tt],l  ,m,L,R);
    if(R> m)  ans+=query(rs[ss],rs[tt],m+1,r,L,R);
    return ans ;
}

int main(){

    while(~scanf("%d",&n)){
        tot=0;
        memset(vis,0,sizeof(vis));
        memset(rt,0,sizeof(rt));

        for(int i=1;i<=n;i++) scanf("%d",a+i),b[i]=a[i];
        sort(b+1,b+n+1);
        int sz=unique(b+1,b+n+1)-(b+1);

        for(int i=0;i<=n;i++) vis[i]=0;

        tot = 0;
        build(rt[0],1,n);
        for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+sz+1,a[i])-b;
//        for(int i=1;i<=n;i++) printf("%d%c",b[i],(i==n)?'\n':' ');
//        for(int i=1;i<=n;i++) printf("%d%c",a[i],(i==n)?'\n':' ');

        int tem;
        for(int i=1;i<=n;i++){
            tem=rt[i-1];
            if(vis[a[i]])update(tem,1,n,rt[i-1],vis[a[i]],-1);
            update(rt[i],1,n,tem,i,1);
            vis[a[i]]=i;
        }

        scanf("%d",&q);
        while(q--){
            scanf("%d%d",&ql,&qr);
            printf("%d\n",query(rt[ql-1],rt[qr],1,n,ql,qr));
        }
    }
    return 0;
}