【传送门：】

---

简要题意：

　　给出一个长度为n的数列，给出m个询问，每个询问输入l,r，输出数列中l到r的不同的数的个数

---

题解：

　　看这数据范围就不能用在线来做，那就只能离线了

　　很显然就是树状数组

　　首先将询问按照l从小到大的排序排一遍

　　设一个数组next，next[i]表示下一个与第i个数相同的数的位置

　　我们从左到右扫一遍数列，如果扫到x这个位置，将x这个位置--，就next[x]这个位置++，然后就通过求前缀和的方法来得出每个询问的答案就可以了

---

参考代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;int k[51000];struct question{    int l,r,d,id;}q[210000];bool cmp(question n1,question n2){
   return n1.l
          
           =1;i--) { next[i]=c[k[i]]; c[k[i]]=i; } memset(a,0,sizeof(a)); for(int i=1;i<=1000000;i++) if(c[i]!=0) change(c[i],1); int l=1; for(int i=1;i<=m;i++) { while(l