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

Tabris

CSDN数据结构SPOJ

发布于：2017年3月11日

次浏览

[原创]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]$区间不同元素的个数

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

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

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

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

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

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

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

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

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

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 而下面的却不能

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

最后也没弄明白怎么回事

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

/***
树状数组离线
*/
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;
}

本页文档最后更新于：2021年5月4日

CSDN

[原创]第四届山东省赛 A-Number and B-Number [数位dp+二分答案]【动态规划】

[原创]第四届山东省赛 A-Number and B-Number [数位dp+二分答案]【动态规划】 2017-03-11 23:13:13 Tabris_ 阅读数：375 博客爬取于20...

[原创]POJ 2104 K-th Number [主席树入门]【数据结构】

[原创]POJ 2104 K-th Number [主席树入门]【数据结构】 2017-03-10 21:51:50 Tabris_ 阅读数：487 博客爬取于2020-06-14 22:...