SPOJ DQUERY D-query （在线主席树/ 离线树状数组）-白红宇

SPOJ DQUERY D-query （在线主席树/ 离线树状数组）

阅读量：5868 次

发布时间：2019-06-19

本文共 2340 字，大约阅读时间需要 7 分钟。

题意：

　　给出一串数，询问[L,R]区间中有多少个不同的数。

解法：

　　关键是查询到某个右端点时，使其左边出现过的数都记录在它们出现的最右位置置1，其他位置置0，然后直接统计[L,R]的区间和就行了。

　　在线和离线都可以做。

　　话不多说，上代码。

在线主席树

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
             10 #define ll long long11 12 using namespace std;13 14 const int N=30000+7;15 const int M=1000000+7;16 17 int Ls[N*20],Rs[N*20],sum[N*20],root[N];18 int tot=0;19 20 int pos[M];21 int a[N];22 int n,q;23 24 inline void copy(int x,int y){25 Ls[x]=Ls[y];26 Rs[x]=Rs[y];27 sum[x]=sum[y];28 }29 30 inline int bulidtree(int L,int R){31 if (L>R) return 0;32 int k=tot++;33 sum[k]=0;34 if (L==R) return k;35 int mid=(L+R)>>1;36 Ls[k]=bulidtree(L,mid);37 Rs[k]=bulidtree(mid+1,R);38 return k;39 } 40 41 inline int update(int o,int p,int v,int L,int R){42 int k=tot++;43 copy(k,o);44 sum[k]+=v;45 46 if (L==R) return k;47 48 int mid=(L+R)>>1;49 if (p<=mid) Ls[k]=update(Ls[k],p,v,L,mid);50 else Rs[k]=update(Rs[k],p,v,mid+1,R);51 52 return k;53 }54 55 inline int query(int o,int x,int y,int L,int R){56 if (L==x && R==y) return sum[o];57 int mid=(L+R)>>1;58 if (y<=mid) return query(Ls[o],x,y,L,mid);59 else if (x>mid) return query(Rs[o],x,y,mid+1,R);60 else return query(Ls[o],x,mid,L,mid)+query(Rs[o],mid+1,y,mid+1,R);61 }62 63 int main(){64 scanf("%d",&n);65 for (int i=1;i<=n;i++) scanf("%d",a+i);66 67 root[0]=bulidtree(1,n);68 69 memset(pos,-1,sizeof(pos));70 for (int i=1;i<=n;i++){71 root[i]=root[i-1];72 if (~pos[a[i]]) 73 root[i]=update(root[i],pos[a[i]],-1,1,n);74 root[i]=update(root[i],i,1,1,n);75 pos[a[i]]=i;76 }77 78 scanf("%d",&q);79 int x,y;80 while (q--){81 scanf("%d %d",&x, &y);82 printf("%d\n",query(root[y],x,y,1,n));83 }84 85 return 0;86 }

离线树状数组

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
             10 #define ll long long11 12 using namespace std;13 14 const int N=30007;15 const int Q=200007;16 const int M=1000007;17 18 struct query{19 int L,R;20 int id;21 bool operator < (const query & t) const {22 return R