( ext{Solution:})
这题看着和 HH的项链 很像。回忆一下：
项链那题我们维护了一个颜色 最右端出现的位置 ，将询问离线排序，每次遇到一个颜色就更新它的位置。
由于询问右端点是递增的，这个做法正确性显然。
那么这个题呢？我们要求一个区间中颜色的次数至少出现两次。
那么，这个时候如果只维护右端的，当左区间在这个颜色上一次出现的位置之后的话，答案就是错误的。
仔细想想，由于我们的询问右端点递增，所以，更需要维护的应该 是两个位置中靠左的那个 。
于是，我们处理出一个位置的前一个出现的位置，并通过树状数组实现单点修改、区间查询就可以完成这题。
代码复杂度很低。这个做法不卡常数。树状数组空间 (O(n)) 即可。时间复杂度一个 $ log .$
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e6+10;
inline int read(){
int s=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch)){
s=s*10-48+ch;
ch=getchar();
}
return s;
}
int tr[MAXN],n,m,c,a[MAXN],ans[MAXN];
int nxt[MAXN],last[MAXN];
struct Q{
int l,r,id;
bool operator<(const Q&B)const{
return r<B.r;
}
}q[MAXN];
inline int lowbit(int x){return x&(-x);}
void change(int x,int v){for(;x<=n;x+=lowbit(x))tr[x]+=v;}
int query(int x){
int res=0;
for(;x;x-=lowbit(x))res+=tr[x];
return res;
}
int main(){
scanf("%d%d%d",&n,&c,&m);
for(int i=1;i<=n;++i){
a[i]=read();
nxt[i]=last[a[i]];
last[a[i]]=i;
}
for(int i=1;i<=m;++i)scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;
sort(q+1,q+m+1);
for(int i=1,j=1;i<=m;++i){
while(j<=q[i].r&&j<=n){
if(nxt[j]==0){
j++;
continue;
}
else if(nxt[j]&&!nxt[nxt[j]]){
change(nxt[j],1);
j++;
continue;
}
else{
change(nxt[nxt[j]],-1);
change(nxt[j],1);
j++;
continue;
}
}
ans[q[i].id]=query(q[i].r)-query(q[i].l-1);
}
for(int i=1;i<=m;++i)printf("%d
",ans[i]);
return 0;
}