不能用分块。
#include <bits/stdc++.h>
using namespace std;
const int Maxn=;
struct Info{int l,r,Id;}Q[Maxn];
int a[Maxn],n,c,m,Last[Maxn],Next[Maxn],d[Maxn],Ans[Maxn];
inline bool Cmp(Info A,Info B) {return A.l>B.l;}
inline int Lowbit(int x) {return x&(-x);}
inline void Add(int x,int v) {for (int i=x;i<=n;i+=Lowbit(i)) d[i]+=v;}
inline int Query(int x) {int Ret=; for (int i=x;i;i-=Lowbit(i)) Ret+=d[i];return Ret;}
int main()
{
// freopen("c.in","r",stdin);
scanf("%d%d%d",&n,&c,&m);
for (int i=;i<=n;i++) scanf("%d",&a[i]);
for (int i=;i<=c;i++) Last[i]=n+;
for (int i=n;i>=;i--)
{
Next[i]=Last[a[i]];
Last[a[i]]=i;
}
Next[n+]=n+;
for (int i=;i<=m;i++) scanf("%d%d",&Q[i].l,&Q[i].r),Q[i].Id=i;
sort(Q+,Q+m+,Cmp); int j=n;
for (int i=;i<=m;i++)
{
while (j && j>=Q[i].l) Add(Next[Next[j]],-),Add(Next[j--],);
Ans[Q[i].Id]=Query(Q[i].r);
}
for (int i=;i<=m;i++) printf("%d\n",Ans[i]);
return ;
}
C++