主席树的又一种写法。 从后端点开始添加主席树， 然后如果遇到出现过的元素先把那个点删除， 再更新树， 最后查询区间就好了。
#include<bits/stdc++.h>
using namespace std;
#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);
#define LL long long
#define ULL unsigned LL
#define fi first
#define se second
#define pb push_back
//#define lson l,m,rt<<1
//#define rson m+1,r,rt<<1|1
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
typedef pair<int,int> pll;
const int INF = 0x3f3f3f3f;
const LL mod = (int)1e9+;
const int N = 3e4 + ;
const int M = 1e6 + ;
int root[N], lson[M], rson[M], cnt[M];
int a[N];
map<int,int> mp;
int tot;
int Build(int l, int r){
int now = ++tot;
cnt[now] = ;
if(l < r){
int m = l+r >> ;
lson[now] = Build(l, m);
rson[now] = Build(m+, r);
}
return now;
}
int Update(int l, int r, int pre, int c, int v){
int now = ++tot;
cnt[now] = cnt[pre] + v;
if(l < r){
int m = l+r >> ;
if(c <= m){
rson[now] = rson[pre];
lson[now] = Update(l, m, lson[pre], c, v);
}
else {
lson[now] = lson[pre];
rson[now] = Update(m+, r, rson[pre], c, v);
}
}
return now;
}
int Query(int l, int r, int p, int R){
if(l == r) return cnt[p];
int m = l+r >> ;
if(R <= m){
return Query(l, m, lson[p], R);
}
else {
return Query(m+,r,rson[p],R) + cnt[lson[p]];
}
}
int main(){
int n;
scanf("%d", &n);
for(int i = ; i <= n; i++) scanf("%d", &a[i]);
root[n+] = Build(, n);
for(int i = n; i >= ; i--){
if(mp[a[i]] == ){
root[i] = Update(, n, root[i+], i, );
}
else {
int tmp = Update(, n, root[i+], mp[a[i]], -);
root[i] = Update(, n, tmp, i, );
}
mp[a[i]] = i;
}
int m, l, r;
scanf("%d", &m);
for(int i = ; i <= m; i++){
scanf("%d%d", &l, &r);
printf("%d\n", Query(,n,root[l],r));
}
return ; }
SPOJ-3267