HH的项链（codevs 2307）

题目描述 Description

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

输入描述 Input Description

第一行：一个整数N，表示项链的长度。

第二行：N个整数，表示依次表示项链中贝壳的编号（编号为0到1000000之间的整数）。

第三行：一个整数M，表示HH询问的个数。

接下来M行：每行两个整数，L和R（1 ≤ L ≤ R ≤ N），表示询问的区间。

输出描述 Output Description

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

样例输入 Sample Input

1 2 3 4 3 5

1 2

3 5

2 6

样例输出 Sample Output

数据范围及提示 Data Size & Hint

对于20%的数据，N ≤ 100，M ≤ 1000；

对于40%的数据，N ≤ 3000，M ≤ 200000；

对于100%的数据，N ≤ 50000，M ≤ 200000。

/*
  线段树(果然比树状数组慢了不少） 
      这道题要离线做，将询问按左边界L从小到大排序，当确保一个位置以后
  一定不会被访问的情况下，将它下一个与它相同的数的所在位置更新，因为
  如果这个位置以后可能被访问，它的下一个位置就不能对答案有贡献。 
      拿样例数据1 2 3 4 3 5来说，第二个3被更新的前提是第一个3不再使用，
  即以后询问出现的左边界L一定大于3。 
*/
#include<cstdio>
#include<iostream>
#include<algorithm>
#define N 50010
#define M 1000010
#define lson l,m,now*2
#define rson m+1,r,now*2+1
using namespace std;
int sum[N*4],next[N],a[N],p[M];
struct node
{
    int L,R,id,ans;
};node e[N*4];
int cmp1(const node&x,const node&y){return x.L<y.L;}
int cmp2(const node&x,const node&y){return x.id<y.id;}
int read()
{
    char c=getchar();int flag=1,num=0;
    while(c<'0'||c>'9'){if(c=='-')flag=-1;c=getchar();}
    while(c>='0'&&c<='9'){num=num*10+c-'0';c=getchar();}
    return flag*num;
}
void push_up(int now)
{
    sum[now]=sum[now*2]+sum[now*2+1];
}
void change(int pos,int l,int r,int now)
{
    if(l==r)
    {
        sum[now]++;
        return;
    }
    int m=(l+r)/2;
    if(pos<=m)change(pos,lson);
    else change(pos,rson);
    push_up(now);
}
int query(int x,int y,int l,int r,int now)
{
    if(l>=x&&r<=y)return sum[now];
    int m=(l+r)/2,ans=0;
    if(x<=m)ans+=query(x,y,lson);
    if(y>m)ans+=query(x,y,rson);
    return ans;
}
int main()
{
    int n=read(),mx=0;
    for(int i=1;i<=n;i++)
      scanf("%d",&a[i]),mx=max(mx,a[i]);
    for(int i=n;i>=1;i--)
      next[i]=p[a[i]],p[a[i]]=i;
    for(int i=1;i<=mx;i++)
      if(p[i])change(p[i],1,n,1);
    int m=read();
    for(int i=1;i<=m;i++)
      scanf("%d%d",&e[i].L,&e[i].R),e[i].id=i;
    sort(e+1,e+m+1,cmp1);
    int l=1;
    for(int i=1;i<=m;i++)
    {
        while(l<e[i].L)
        {
            change(next[l],1,n,1);
            l++;
        }
        e[i].ans=query(e[i].L,e[i].R,1,n,1);
    }
    sort(e+1,e+m+1,cmp2);
    for(int i=1;i<=m;i++)
      printf("%d
",e[i].ans);
    return 0;
}

View Code