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
题意：给定N个数，以及Q个询问，对于每个询问，回答这个区间去重后有多少个数。
思路：询问多，时间紧，用莫队和分块是过不去的。 这里需要用主席树，而且我知道要用主席树后也没有想到这么写。。。写法太神奇了。（我太弱了
这里的主席树记录的是前缀每个位置是否用贡献。对于每个区间[1,i]，它建立在[1,i-1]的基础上。对于最后一个数，即第i个数，考虑它的贡献，如果它之前没有出现相同的数，则贡献为1。否则，把pre的贡献减去1，i的贡献加1。
（这路说它非常规，是因为它记录的是位置，而不是位置上的数
#include<bits/stdc++.h>
using namespace std;
const int maxn=;
struct node{
int val,l,r;
node() { val=l=r=; }
node(int L,int R,int V):l(L),r(R),val(V){}
}s[maxn*];
int rt[maxn],cnt;
map<int,int>mp;
void insert(int &now,int pre,int L,int R,int pos,int val)
{
s[now=++cnt]=node(s[pre].l,s[pre].r,s[pre].val+val); //先假设都等
if(L==R) return ;
int Mid=(L+R)>>;
if(pos<=Mid) insert(s[now].l,s[pre].l,L,Mid,pos,val); //这里再把不等的改掉
else insert(s[now].r,s[pre].r,Mid+,R,pos,val);
}
int query(int now,int pos,int L,int R)
{
if(L==R) return s[now].val;
int Mid=(L+R)>>;
if(pos<=Mid) return query(s[now].l,pos,L,Mid)+s[s[now].r].val;
return query(s[now].r,pos,Mid+,R);
}
int main()
{
int N,Q,x,y,i;
scanf("%d",&N);
for(i=;i<=N;i++){
scanf("%d",&x);
if(!mp[x]) insert(rt[i],rt[i-],,N,i,);
else {
insert(y,rt[i-],,N,mp[x],-);
insert(rt[i],y,,N,i,);
}
mp[x]=i;
}
scanf("%d",&Q);
while(Q--){
scanf("%d%d",&x,&y);
printf("%d\n",query(rt[y],x,,N));
}
return ;
}