HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH 不断地收集新的贝壳，因此，他的项链变得越来越长。有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答……因为项链实在是太长了。于是，他只好求助睿智的你，来解决这个问题。
Input第一行：一个整数N，表示项链的长度。
第二行：N 个整数，表示依次表示项链中贝壳的编号（编号为0 到1000000 之间的整数）。
第三行：一个整数M，表示HH 询问的个数。
接下来M 行：每行两个整数，L 和R（1 ≤ L ≤ R ≤ N），表示询问的区间。
OutputM 行，每行一个整数，依次表示询问对应的答案。
Range对于100%的数据，N <= 500000，M <= 200000。
Solution树状数组+离线处理。
此题首先应该考虑到这样一个结论：
对于若干个询问的区间 \([l,r]\) ，如果他们的 \(r\) 都相等的话，那么项链中出现的同一个数字，一定是值关心出现在最右边的那一个的。例如：
项链是：\(1\;3\;4\;5\;1\)
那么，对于 \(r=5\) 的所有的询问来说，第一个位置上的 \(1\) 完全没有意义，因为\(r\)已经在第五个 \(1\) 的右边，对于任何查询的 \([L,5]\) 区间来说，如果第一个 \(1\) 被算了，那么他完全可以用第五个 \(1\) 来替代。
因此，我们可以对所有查询的区间按照 \(r\) 来排序，然后再来维护一个树状数组，这个树状数组是用来干什么的呢？看下面的例子：
\(1\;2\;1\;3\)
对于第一个 \(1\)，\(insert(1,1)\) 表示第一个位置出现了一个不一样的数字，此时树状数组所表示的每个位置上的数字（不是它本身的值而是它对应的每个位置上的数字）是：\(1\;0\;0\;0\)
对于第二个 \(2\) ，\(insert(2,1)\) 此时树状数组表示的每个数字是 \(1\;1\;0\;0\)
对于第三个 \(1\)，因为之前出现过 \(1\) 了，因此首先把那个 \(1\) 所在的位置删掉insert(1,-1)$ ,然后在把它加进来 \(insert(3,1)\)。此时每个数字是 \(0\;1\;1\;0\)
如果此时有一个询问 \([2,3]\)，那么直接求 \(query(3)-query(2-1)=2\) 就是答案。
摘自题解
#include<cstdio> #include<algorithm> #define N 500005 #define M 200005 int n,m; int f[N]; int val[N]; int out[M]; int last[N<<1]; bool comeup[N<<1]; struct Question{ int l,r,idx; friend bool operator<(Question a,Question b){ if(a.r!=b.r) return a.r<b.r; return a.l<b.l; } }ques[M]; void add(int x,int k){ for(;x<=n;x+=x&-x) f[x]+=k; } int query(int x){ int tot=0; for(;x;x-=x&-x) tot+=f[x]; return tot; } signed main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&val[i]); scanf("%d",&m); for(int i=1;i<=m;i++){ scanf("%d%d",&ques[i].l,&ques[i].r); ques[i].idx=i; } std::sort(ques+1,ques+1+m); int now=0; for(int i=1;i<=m;i++){ while(now<ques[i].r){ now++; if(!comeup[val[now]]){ comeup[val[now]]=1; last[val[now]]=now; add(now,1); } else{ add(last[val[now]],-1); add(now,1); last[val[now]]=now; } } out[ques[i].idx]=query(ques[i].r)-query(ques[i].l-1); } for(int i=1;i<=m;i++) printf("%d\n",out[i]); return 0; }