题目链接：

题意：给出一个数列，每次询问区间[L,R]中有多少个不同的数字？

思路：

（1）记录每个位置i的数字的前一个相同数字出现的位置pre[i]，没有前一个相同的pre[i]为0。

（2）询问按照R升序。

（3）开始计算：枚举i从1到m（m为询问个数），对于某个位置x，将pre[x]+1增加1，x+1减少1，这样做的原因在于任意一个数字在任意一段区间中最多出现一次。然后统计左区间之前的和即可。

 

int s[N];

void add(int x,int t)

{

    while(x<N)

    {

        s[x]+=t;

        x+=x&-x;

    }

}

int get(int x)

{

    int ans=0;

    while(x)

    {

        ans+=s[x];

        x-=x&-x;

    }

    return ans;

}

int a[N],pre[N],last[N],n;

struct node

{

    int L,R,id;

};

node b[N];

int m,ans[N];

int cmp(node a,node b)

{

    return a.R<b.R;

}

int main()

{

    RD(n);

    int i;

    FOR1(i,n)

    {

        RD(a[i]);

        pre[i]=last[a[i]];

        last[a[i]]=i;

    }

    RD(m);

    FOR1(i,m) RD(b[i].L,b[i].R),b[i].id=i;

    sort(b+1,b+m+1,cmp);

    int now=0;

    FOR1(i,m)

    {

        while(now<b[i].R)

        {

            now++;

            add(pre[now]+1,1);

            add(now+1,-1);

        }

        ans[b[i].id]=get(b[i].L);

    }

    FOR1(i,m) PR(ans[i]);

}