HH有一串由各种漂亮的贝壳组成的项链。HH相信不同的贝壳会带来好运，所以每次散步 完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH不断地收集新的贝壳，因此， 他的项链变得越来越长。有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同 的贝壳？这个问题很难回答。。。因为项链实在是太长了。于是，他只好求助睿智的你，来解 决这个问题。

第一行：一个整数N，表示项链的长度。 第二行：N个整数，表示依次表示项链中贝壳的编号（编号为0到1000000之间的整数）。 第三行：一个整数M，表示HH询问的个数。 接下来M行：每行两个整数，L和R（1 ≤ L ≤ R ≤ N），表示询问的区间。

M行，每行一个整数，依次表示询问对应的答案。

6
1 2 3 4 3 5
3
1 2 
3 5
2 6

2 
2 
4

题目分析：

神思路
先将询问区间离线 排序 记录原序列的每个相等数字的位置 把每一个第一次出现的数字加入到树状数组里
然后从1开始 往后移动 经过一个数就把它从树状数组里扔掉 并把它下一个出现的位置插入树状数组
每到一个区间右端点 向下查询 这样就A了这道题

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m;
struct my
{
    int c,id;
}a[51000];
int net[51000];
int f[51000];
bool book[1010000];
bool vis[51000];
int ans[510000];
struct your
{
    int x;
    int y;
    int id;
    int c;
}b[210000];
bool cmp(your j,your k)
{
    if(j.x==k.x) return j.y<k.y;
    return j.x<k.x;
}
bool cmp2(my j,my k)
{
    if(j.c==k.c) return j.id<k.id;
    return j.c<k.c;
}
void update(int x,int c)
{
    for(;x<=n;x+=x&-x)
        f[x]+=c;
}
int ask(int x)
{
    int tmp=0;
    for(;x;x-=x&-x)
        tmp+=f[x];
    return tmp;
}
int cnt;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i].c),a[i].id=i;
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
        scanf("%d%d",&b[i].x,&b[i].y),b[i].id=i;
    sort(b+1,b+m+1,cmp);
    sort(a+1,a+n+1,cmp2);
    for(int i=1;i<=n;i++)
    {
        if(!book[a[i].c])
        {
            update(a[i].id,1);
            book[a[i].c]=1;
            vis[a[i].id]=1;
        }
        if(a[i+1].c==a[i].c)
            net[a[i].id]=a[i+1].id;
    }
    for(int i=1;i<=n;i++)
    {
        if(i==b[cnt+1].x&&cnt<m)
            while(i==b[cnt+1].x&&cnt<m)
            {
                cnt++;
                ans[b[cnt].id]=ask(b[cnt].y);
            }
        if(vis[i]==1)
        {
            update(i,-1),vis[i]=0,vis[net[i]]=1;
            if(net[i]!=0) update(net[i],1);
        }
    }
    for(int i=1;i<=m;i++)
        printf("%d\n",ans[i]);
    return 0;
}