题目链接：

　　怎么说呢这道题，它出现在树状数组的练习里，那必然树状数组是可以解决的。一开始没有思路，但被大佬的几句话点开了。有人说是 离线+树状数组 ，但我觉得不是离线，毕竟最后是循环输出的。

　　假如 a_l~r 之间有多个编号为 k 的贝壳，那么询问一个区间 [i,r] 时，可以总是让最靠右的贝壳来计数。因为相同的数只计一次，每当再次遇到 k 时，可以取消左边 k 的计数，来让右边的 k 计数。也就是说我们可以建树状数组用来维护 [1,pos] 的不同贝壳数，其中相同编号的贝壳 总让最右边的生效。那么read（pos）的返回值就是区间[1,pos]的不同数字个数。就可以先获取所有的区间，按 r 升序，当前下标 i ==r 时，就可以 询问得到此区间的答案。

先看代码：

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #define lowb(a) a&-a;/**< 比函数快那么几百毫秒 */using namespace std;const int N=5*1e5+10;const int M=2*1e5+10;int n,m;int a[N];int t[N],ha[2*N];/**< 很坑的就是这个1e6了 */struct range{ int l; int r; int no;/**< 打乱的顺序，要重排 */ int ans;}g[M];bool cmp1(range a,range b){ return a.r
             
              0) { res+=t[k]; k-=lowb(k); } return res;}int range_ask(int l,int r){ return read(r)-read(l-1);}int main(){ /**< 树状数组下标没有0，那都从1开始 */ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); scanf("%d",&m); for(int i=1;i<=m;i++) { scanf("%d%d",&g[i].l,&g[i].r); g[i].no=i; } sort(g+1,g+m+1,cmp1); int cnt=1; for(int i=1;i<=n;i++) { if(!ha[a[i]]) { p_add(i,1); ha[a[i]]=i; } else { p_add(ha[a[i]],-1); p_add(i,1); ha[a[i]]=i; } while(i==g[cnt].r)/**< 不是if，因为会存在r相同的区间 */ { g[cnt].ans=range_ask(g[cnt].l,g[cnt].r); cnt++; } } sort(g+1,g+m+1,cmp2); for(int i=1;i<=m;i++) printf("%d\n",g[i].ans); return 0;}
             
            
           
          
         
        
       
      

 树状数组维护的只是 位置（下标 i ）的信息（不清楚的，可以计算每一步的 树状数组的值）。过程是：

1. a_i 的value是否出现过
2. 否则p_add(i,1),记录 下标i；
3. 是则p_add(记录的i，-1),更新记录；
4. 检查是否已有区间被包含。回到 1

　　举个样例，项链长度为 7，6 个区间询问。项链的编号（如图1）：a₁=1   a₂=4   a₃=3    a₄=4 ······a₇=3 。

Input71 4 3 4 2 1 362 71 32 43 51 42 6Output432334