1 #include <cstdio> 2 #include <algorithm> 3 struct que 4 { 5     int l,r,id; 6 } q[1000001]; 7 bool operator<(que a,que b){return a.r<b.r;} 8 int n,l[1000001],an,c,m,o[1000001],pre[1000001],co[1000001],ans[1000001]; 9 void add(int a,int b)10 {11     while(a<=n)12         l[a]+=b,a+=a&-a;13 }14 int get(int a)15 {16     for(an=0;a;a-=a&-a)17         an+=l[a];18     return an;19 }20 int main()21 {22     scanf("%d%d%d",&n,&c,&m);23     for(int i=1;i<=n;i++)24         scanf("%d",&o[i]),pre[i]=co[o[i]],co[o[i]]=i;25     for(int i=1;i<=m;i++)26         scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;27     std::sort(q+1,q+m+1);28     int rnow=0;29     for(int i=1;i<=m;i++)30     {31         while(rnow<q[i].r) 32             if(pre[++rnow]>0)33                 add(pre[pre[rnow]]+1,1),add(pre[rnow]+1,-1);34         ans[q[i].id]=get(q[i].l);35     }36     for(int i=1;i<=m;i++)37         printf("%d\n",ans[i]);38     return 0;39 }