| 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 5 1 1 2 1 3 3 1 5 2 4 3 5 Output 3 2 3
题目链接：SPOJ 3267
假设数组从1开始，以当前数字的位置（下标）为pos，贡献为1，用主席树维护前缀序列[1，i]的贡献和，则显然第i棵线段树就是对应的前缀序列[1，i]，题目给出l与r，r可直接用，显然l还不对需要转换，我这里写的和其他人的做法不太一样，还是用区间内的区间求和思想。即对root[l-1]~root[r]求l~r的区间和。因为用的是下标而不是原值更不是离散化之后的值作插入位置，因此l,r既是询问区间也是求和区间。一开始范围搞错了把离散化之后的size作为值域大小，wa数次……，此外这题似乎还可以莫队或者离线树状数组搞搞，前者太模版了就懒的写了3W的数据量估计是可以莫队暴力过的，后者……理解不够深入就先不贴代码了
代码：
#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
typedef pair<int,int> pii;
typedef long long LL;
const double PI=acos(-1.0);
const int N=30010;
struct seg
{
int lson,rson;
int cnt;
};
seg T[N*20];
int root[N],tot;
vector<int>pos;
int arr[N];
int last_pos[N];
void init()
{
pos.clear();
CLR(root,0);
tot=0;
T[0].cnt=T[0].lson=T[0].rson=0;
CLR(last_pos,0);
}
void update(int &cur,int ori,int l,int r,int pos,int flag)
{
cur=++tot;
T[cur]=T[ori];
T[cur].cnt+=flag;
if(l==r)
return ;
int mid=MID(l,r);
if(pos<=mid)
update(T[cur].lson,T[ori].lson,l,mid,pos,flag);
else
update(T[cur].rson,T[ori].rson,mid+1,r,pos,flag);
}
int query(int S,int E,int l,int r,int x,int y)
{
if(x<=l&&r<=y)
return T[E].cnt-T[S].cnt;
else
{
int mid=MID(l,r);
if(y<=mid)
return query(T[S].lson,T[E].lson,l,mid,x,y);
else if(x>mid)
return query(T[S].rson,T[E].rson,mid+1,r,x,y);
else
return query(T[S].lson,T[E].lson,l,mid,x,mid)+query(T[S].rson,T[E].rson,mid+1,r,mid+1,y);
}
}
int main(void)
{
int n,m,i,l,r;
while (~scanf("%d",&n))
{
init();
for (i=1; i<=n; ++i)
{
scanf("%d",&arr[i]);
pos.push_back(arr[i]);
}
scanf("%d",&m);
sort(pos.begin(),pos.end());
pos.erase(unique(pos.begin(),pos.end()),pos.end());
int temp_rt=0;
for (i=1; i<=n; ++i)
{
arr[i]=lower_bound(pos.begin(),pos.end(),arr[i])-pos.begin()+1;
if(!last_pos[arr[i]])
{
update(root[i],root[i-1],1,n,i,1);
last_pos[arr[i]]=i;
}
else
{
update(temp_rt,root[i-1],1,n,last_pos[arr[i]],-1);
update(root[i],temp_rt,1,n,i,1);
last_pos[arr[i]]=i;
}
}
for (i=0; i<m; ++i)
{
scanf("%d%d",&l,&r);
printf("%d\n",query(root[l-1],root[r],1,n,l,r));
}
}
return 0;
}
SPOJ 3267 D-query（离散化+主席树求区间内不同数的个数）
原文：http://www.cnblogs.com/Blackops/p/5958796.html