题链：
http://www.lydsy.com/JudgeOnline/problem.php?id=2743
题解：
树状数组，离线
求区间里面有多少种出现次数大于等于 2 的颜色。
类似某一个题，问的是区间里面有多少种不同的颜色(即出现次数大于等于 1 )。
把询问离线，并按右端点 r 从小到大排序。
并维护出 last[i] 表示与 i 位置颜色相同的上一个位置。
然后从左到右枚举右端点 i，
在树状数组中把 last[last[i]] 位置(如果不为 0 的话)的值 -1，
把 last[i] 位置(如果不为 0 的话)的值 +1
(也就是只给距离当前枚举到的 i位置第二近的并且和i位置颜色相同的那个位置打上标记)
然后回答右端点在 i 处的询问即可。
代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAXN 1000500
using namespace std;
int last[MAXN],pos[MAXN],ANS[MAXN];
int N,C,M;
struct Question{
int l,r,id;
bool operator <(const Question &rtm)const{
return r<rtm.r;
}
}Q[MAXN];
struct BIT{
int A[MAXN],N;
void Reset(int n){N=n;}
int Lowbit(int x){return x&-x;}
void Modify(int p,int x){
while(p<=N) A[p]+=x,p+=Lowbit(p);
}
int Query(int p){
static int ret; ret=0;
while(p) ret+=A[p],p-=Lowbit(p);
return ret;
}
}DT;
char gc(){
static char s[300010];
static int bit=300000,len,p;
if(p>=len) len=fread(s,1,bit,stdin),s[len]=EOF,p=0;
return s[p++];
}
void read(int &x){
static int f; static char ch;
x=0; f=1; ch=gc();
while(ch<'0'||'9'<ch){if(ch=='-')f=-1;ch=gc();}
while('0'<=ch&&ch<='9'){x=x*10+ch-'0';ch=gc();}
x=x*f;
}
void write(int x){
static char s[20]; static int p;
if(!x) putchar('0');
if(x<0) putchar('-'),x=-x;
while(x) s[p++]=x%10+'0',x/=10;
while(p) putchar(s[--p]);
putchar('
');
}
int main(){
read(N); read(C); read(M);
for(int i=1,a;i<=N;i++)
read(a),last[i]=pos[a],pos[a]=i;
for(int i=1;i<=M;i++)
read(Q[i].l),read(Q[i].r),Q[i].id=i;
sort(Q+1,Q+M+1);
DT.Reset(N);
for(int i=1,j=1;i<=N;i++){
if(last[last[i]]) DT.Modify(last[last[i]],-1);
if(last[i]) DT.Modify(last[i],1);
while(Q[j].r==i&&j<=M){
ANS[Q[j].id]=DT.Query(Q[j].r)-DT.Query(Q[j].l-1);
j++;
}
}
for(int i=1;i<=M;i++) write(ANS[i]);
return 0;
}