【SDOI2009】HH的项链线段树

题目描述

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

输入输出格式

输入格式：

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

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

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

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

输出格式：

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

输入输出样例

输入样例#1：

6

1 2 3 4 3 5

3

1 2

3 5

2 6

输出样例#1：

数据范围：

对于100%的数据，N <= 500000，M <= 500000。

---------------------------------------------------------------------------------------------------

这个数据一看就不能暴力标记什么的水过去

然后看到维护和询问的区间信息所以很快想到了线段树

关键是维护的序列是什么呢？

我们选择维护一个1~n的序列对每个点：为0表示此时下标表示的数不存在，为1表示此时下标表示的数存在

我们选择离线做法，先记录下每次询问一边处理每个值一边查询

将询问按照右端点排序，now记录当前访问到的询问

记last[i]数组表示 i上一次出现的位置（即截止目前最后出现的位置

用一遍for循环 update贝壳的编号进入序列即update(1,i,1); 表示现在在当前位出现

然后将上一次出现i的位置重置为0 即 update(1,last[a[i]],0); 并记下i出现的当前新位置last[a[i]]=i;

对于询问每次从处理好的询问中找出右端点和当前处理位置相同的询问进行查询

怎样查询呢？

因为每一次我们只记录下了每个值最后出现的位置以前的早已清零，所以查询一段区间中有多少的不同值就是做区间求和

于是就变成线段树的基本操作了ovo

注：1.注意线段树中查询操作的写法

　　2.注意开够数组

贴个代码

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cmath>

 #include<cstring>

 #define N 500100

 #define lc p<<1

 #define rc p<<1|1

 using namespace std;

 int n,m;

 int a[N];

 struct node

 {

     int l,r,val;

 }t[N<<];

 struct pu

 {

     int x,y,id,ans;

 }q[N];

 bool cmp(pu a,pu b) { return a.y<b.y; }

 bool cmp1(pu a,pu b) { return a.id<b.id; }

 void pushup(int p){

     t[p].val=t[lc].val+t[rc].val;

 }

 void build(int p,int l,int r)

 {

     t[p].l=l; t[p].r=r;

     if(l==r) return;

     int mid=l+r>>;

     build(lc,l,mid);

     build(rc,mid+,r);

     pushup(p);

 }

 void update(int p,int x,int v)

 {

     if(t[p].l==t[p].r)

     {

         t[p].val=v;

         return;

     }

     int mid=t[p].l+t[p].r>>;

     if(x<=mid) update(lc,x,v);

     else update(rc,x,v);

     pushup(p);

 }

 int query(int p,int ql,int qr)

 {

     //if(t[p].l<ql||t[p].r>qr) return 0;

     if(ql<=t[p].l&&t[p].r<=qr)

         return t[p].val;

     int ans=;

     int mid=t[p].l+t[p].r>>;

     if(ql<=mid) ans+=query(lc,ql,qr);

     if(qr>mid) ans+=query(rc,ql,qr);

     return ans;

 }

 int last[];

 int main()

 {

     scanf("%d",&n);

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

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

     scanf("%d",&m);

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

     {

         scanf("%d%d",&q[i].x,&q[i].y);

         q[i].id=i;

     }

     build(,,n);

     int now=;

     sort(q+,q+m+,cmp);

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

     {

         update(,i,);

         if(last[a[i]]) update(,last[a[i]],);

         last[a[i]]=i;

         while(q[now].y==i)

         {

             q[now].ans=query(,q[now].x,q[now].y);

             now++;

         }

     }

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

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

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

     return ;

 }

项链