题目连接: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,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,print the number of distinct elements in the subsequence ai,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次询问，
询问
解题思路：
本来是做的主席树专题 ，然而主席树怎么做 还不会，
于是就用离线树状数组的做法水了一发
主要就是对询问的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],tem,i,1); vis[a[i]]=i; }
上面的能AC 而下面的却不能
for(int i=1;i<=n;i++){ if(vis[a[i]])update(rt[i],rt[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 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],m,ls[last],pos,v);
else update(rs[rt],rs[last],v);
}
int query(int ss,int tt,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,R);
if(R> m) ans+=query(rs[ss],rs[tt],R);
return ans ;
}
int main(){
while(~scanf("%d",&n)){
tot=0;
memset(vis,0,sizeof(vis));
memset(rt,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],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);
update(rt[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],qr));
}
}
return 0;
}
