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*],next[N],a[N],p[M];

struct node

{

    int L,R,id,ans;

};node e[N*];

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=,num=;

    while(c<''||c>''){if(c=='-')flag=-;c=getchar();}

    while(c>=''&&c<=''){num=num*+c-'';c=getchar();}

    return flag*num;

}

void push_up(int now)

{

    sum[now]=sum[now*]+sum[now*+];

}

void change(int pos,int l,int r,int now)

{

    if(l==r)

    {

        sum[now]++;

        return;

    }

    int m=(l+r)/;

    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)/,ans=;

    if(x<=m)ans+=query(x,y,lson);

    if(y>m)ans+=query(x,y,rson);

    return ans;

}

int main()

{

    int n=read(),mx=;

    for(int i=;i<=n;i++)

      scanf("%d",&a[i]),mx=max(mx,a[i]);

    for(int i=n;i>=;i--)

      next[i]=p[a[i]],p[a[i]]=i;

    for(int i=;i<=mx;i++)

      if(p[i])change(p[i],,n,);

    int m=read();

    for(int i=;i<=m;i++)

      scanf("%d%d",&e[i].L,&e[i].R),e[i].id=i;

    sort(e+,e+m+,cmp1);

    int l=;

    for(int i=;i<=m;i++)

    {

        while(l<e[i].L)

        {

            change(next[l],,n,);

            l++;

        }

        e[i].ans=query(e[i].L,e[i].R,,n,);

    }

    sort(e+,e+m+,cmp2);

    for(int i=;i<=m;i++)

      printf("%d\n",e[i].ans);

    return ;

}

巴特西

HH的项链（codevs 2307）

最新文章

热门文章