http://www.lydsy.com/JudgeOnline/problem.php?id=1878

题意

给定一个序列，询问每个区间上有多少不同的数字。

题解

因为没有修改，所以离线做就可以了。

把询问按右端点排序，

从前到后，对于每个颜色，

在它上一次出现的地方的后一点+1，

在当前位置的后一点-1；

当前询问答案为ΣXi（1..L)

#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int N=1000002;
int n,m;
struct rec{int n,x,y;}a[N];
int color[N],last[N],pre[N],ans[N];
int c[N];
inline bool cmp(rec a,rec b)
{
  return a.y<b.y;
}
inline void inc(int x,int w)
{
  for(;x<=n;x+=lowbit(x))c[x]+=w;
}
inline int sum(int x)
{
  int s=0;
  for(;x;x-=lowbit(x))s+=c[x];
  return s;
}
 
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
	{
        scanf("%d",color+i);
        pre[i]=last[color[i]];
        last[color[i]]=i;
    }
    scanf("%d",&m);
    for(int i=0;i<m;++i)
    {
        scanf("%d%d",&a[i].x,&a[i].y);
        a[i].n=i;
    }
    sort(a,a+m,cmp);
    int now=0;
    for(int i=0;i<m;++i)
    {
        while(now<a[i].y)
            inc(pre[++now]+1,1),inc(now+1,-1);
        ans[a[i].n]=sum(a[i].x);
    }
 	for(int i=0;i<m;++i)printf("%d\n",ans[i]);
}