题目大意

给出$n$个数的数列，提出$m$次询问,每次询问区间$[l,r]$中有多少种数字

比如在数列$“1 2 3 4 3 5”$，在区间$[3,5]$中有两种数字$“3,4”$

数据范围

$n\leqslant 50000,m\leqslant 200000$,数列里每一个数字$0\leqslant a_i\leqslant 1000000$

题解

$first[]$记录每一种数字第一个出现的位置，$next[]$记录每个位置上那种数字下一次出现的位置

初始的时候$first[]$加入前缀和，把每个询问按照左端点为第一关键字，右端点为第二关键字排序

那么此时每次询问的左边界一定是单调递增的，所以搜过的可以不用管它，因为后面的操作和它没有关系

所以搜过一个已经加入前缀和的一种数字的位置i，只需要将$next[i]$加入前缀和，原来的不用删除

询问$[l,r]$,按照前缀和得到$query(r)-query(l-1)$就行了

关于前缀和的操作，可以用树状数组

程序

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Ford(i,r,l) for(int i=r;i>=l;i--)
#define inf 0x7fffffff
using namespace std;

int n,m,mx;
int a[50500],t[50500];
int first[1005000],next[50500];
struct data{int l,r,id,ans;}q[200500];
inline int lowbit(int x){return x&(-x);}
inline int cmp_1(data a,data b){return a.l==b.l?a.r<b.r:a.l<b.l;}
inline int cmp_2(data a,data b){return a.id<b.id;}

inline void updata(int x,int c){
    for(int i=x;i<=n;i+=lowbit(i)) t[i]+=c;
}
inline int query(int x){
    int result=0;
    for(int i=x;i>=1;i-=lowbit(i)) result+=t[i];
    return result;
}
int main(){
    scanf("%d",&n);
    For(i,1,n){scanf("%d",&a[i]);mx=max(mx,a[i]);}
    Ford(i,n,1){next[i]=first[a[i]];first[a[i]]=i;}
    For(i,1,mx) if (first[i]) updata(first[i],1);
    scanf("%d",&m);
    For(i,1,m){scanf("%d%d",&q[i].l,&q[i].r);q[i].id=i;}
    sort(q+1,q+m+1,cmp_1);int l=1;
    For(i,1,m){
        while(l<q[i].l){
            if (next[l]) updata(next[l],1);
            ++l;
        }
        q[i].ans=query(q[i].r)-query(q[i].l-1);
    }
    sort(q+1,q+m+1,cmp_2);
    For(i,1,m) printf("%d\n",q[i].ans);
    return 0;
}