1878. [SDOI2009]HH的项链【线段树或莫队】

Description

HH有一串由各种漂亮的贝壳组成的项链。HH相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一

段贝壳，思考它们所表达的含义。HH不断地收集新的贝壳，因此他的项链变得越来越长。有一天，他突然提出了一

个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答。。。因为项链实在是太长了。于是，他只

好求助睿智的你，来解决这个问题。

Input

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

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

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

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

N ≤ 50000，M ≤ 200000。

Output

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

Sample Input

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

Sample Output

2
2
4

第一个线段树第二个莫队

线段树：
啊这个题的IDEA炒鸡妙啊……让我情不自禁想写一发题解
（其实是我怕这次抄题解会了后下次就不会了……）
我们先将询问按照结束点升序排序
用now保存当前询问的是第几个
线段树保存的是当前下标是否有珠子（0/1表示）
然后从1~n依次访问项链。
当前访问中，我们要做的有两件事：
第一件：将当前点的珠子修改成1
第二件：将上一个和当前珠子编号相同的珠子设为0
          （因为我们要保证当前序列里不能有重复编号的珠子
           而当前珠子以后的访问都不需要上一个重复编号的珠子了
           因为我们完全可以用当前珠子来统计区间[L,R]之间的个数
           如何统计呢？求个和就好了啊……）
将当前珠子的修改做好后，就要查询了。如果当前询问(now)的右端点和当前珠子是一样的
就查询[L,R]的和就好了，这个和就代表着区间内不同种的数量
毕竟我们已经把重复的珠子都去重了……

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 struct node
 7 {
 8     int x,y,num,ans;
 9 }ask[200001];
10 struct node1
11 {
12     int val;
13 }Segt[200001];
14 bool cmp(node a,node b)
15 {
16     return a.y<b.y;
17 }
18 bool cmp1(node a,node b)
19 {
20     return a.num<b.num;
21 }
22 
23 int last[1000001],a[50001];
24 int Query(int node,int l,int r,int l1,int r1)
25 {
26     if (l>r1 || r<l1)
27         return 0;
28     if (l1<=l && r<=r1)
29         return Segt[node].val;
30     int mid=(l+r)/2;
31     return Query(node*2,l,mid,l1,r1)+
32            Query(node*2+1,mid+1,r,l1,r1);
33 }
34 
35 void Update(int node,int l,int r,int x,int k)
36 {
37     if (l==r)
38         Segt[node].val=k;
39     else
40     {
41         int mid=(l+r)/2;
42         if (x<=mid)    Update(node*2,l,mid,x,k);
43         else Update(node*2+1,mid+1,r,x,k);
44         Segt[node].val=Segt[node*2].val+Segt[node*2+1].val;
45     }
46 }
47 
48 int main()
49 {
50     int n,m;
51     scanf("%d",&n);
52     for (int i=1;i<=n;++i)
53         scanf("%d",&a[i]);
54     scanf("%d",&m);
55     for (int i=1;i<=m;++i)
56     {
57         scanf("%d%d",&ask[i].x,&ask[i].y);
58         ask[i].num=i;
59     }
60     sort(ask+1,ask+m+1,cmp);
61     int now=1;
62     for (int i=1;i<=n;++i)
63     {
64         Update(1,1,n,i,1);
65         if (last[a[i]]!=0)
66             Update(1,1,n,last[a[i]],0);
67         last[a[i]]=i;
68         while (ask[now].y==i)
69         {
70             ask[now].ans=Query(1,1,n,ask[now].x,ask[now].y);
71             ++now;
72         }
73     }
74     sort(ask+1,ask+m+1,cmp1);
75     for (int i=1;i<=m-1;++i)
76         printf("%d
",ask[i].ans);
77     printf("%d",ask[m].ans);
78 }

莫队：

入门题

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<cmath>
 5 #include<algorithm>
 6 #define MAXN (1000000+10)
 7 using namespace std;
 8 struct node
 9 {
10     int l,r,ord,id,ans;
11 }Ask[MAXN];
12 int l=1,r=0,now,n,m;
13 int cnt[MAXN],a[MAXN]; 
14 bool cmp1(node a,node b){return a.id==b.id?a.r<b.r:a.id<b.id;}
15 bool cmp2(node a,node b){return a.ord<b.ord;}
16 
17 void Del(int x)
18 {
19     cnt[a[x]]--;
20     if (!cnt[a[x]]) now--;
21 }
22 void Ins(int x)
23 {
24     if (!cnt[a[x]]) now++;
25     cnt[a[x]]++;
26 }
27 void MO(int x)
28 {
29     int L=Ask[x].l,R=Ask[x].r;
30     while (l>L) Ins(--l);
31     while (l<L) Del(l++);
32     while (r>R) Del(r--);
33     while (r<R) Ins(++r);
34     Ask[x].ans=now;
35 }
36 
37 int main()
38 {
39     scanf("%d",&n);
40     int len=sqrt(n);
41     for (int i=1;i<=n;++i)
42         scanf("%d",&a[i]);
43     scanf("%d",&m);
44     for (int i=1;i<=m;++i)
45     {
46         scanf("%d%d",&Ask[i].l,&Ask[i].r);
47         Ask[i].id=Ask[i].l/len;
48         Ask[i].ord=i;
49     }
50     sort(Ask+1,Ask+m+1,cmp1);
51     for (int i=1;i<=m;++i)
52         MO(i);
53     sort(Ask+1,Ask+m+1,cmp2);
54     for (int i=1;i<=m;++i)
55         printf("%d
",Ask[i].ans);
56 }