洛谷P1972 [SDOI2009]HH的项链题解

[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：

2
2
4

说明

数据范围：

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

——————————————————————我是分割线——————————————————————————

好题。

这题做法极多（e.g.树状数组、主席树等，甚至可以用各种诡异的做法来A）

但这里用莫队算法。

虽然原理早就懂了，但还是第一次写。(≧∀≦)ゞ好激动~

看到这题，第一时间想到莫队算法（毕竟是区间神器），但不知为何标签里没有（滑稽），于是自写一个。
题目大意：给n个数，m个询问，每个询问要求求出 l~r 之间出现了多少个不同的数字。

我们可以对区间进行分块以提高效率。根据分块算法的套路，以sqrt(n)为一个区间的长度。我们把询问以l为关键字从小到大排序，然后把l在当前区间的询问放在一组。然后呢，对于分到一组的询问，进行r为关键字从小到大的排序。然后进行暴力扫。

总复杂度为 O(m* sqrt(n)+sqrt(m)*n)，还是可以接受的。

下面上代码：

 1 /*
 2     Problem:[SDOI2009]HH的项链
 3     OJ:洛谷
 4     User:S.B.S.
 5     Time:N/A
 6     Memory:N/A
 7     Length:N/A
 8 */
 9 #include<iostream>
10 #include<cstdio>
11 #include<cstring>
12 #include<cmath>
13 #include<algorithm>
14 #include<queue>
15 #include<cstdlib>
16 #include<iomanip>
17 #include<cassert>
18 #include<climits>
19 #include<functional>
20 #include<bitset>
21 #include<vector>
22 #include<list>
23 #define F(i,j,k) for(int i=j;i<=k;++i)
24 #define M(a,b) memset(a,b,sizeof(a))
25 #define FF(i,j,k) for(int i=j;i>=k;i--)
26 #define maxn 50001
27 #define inf 0x3f3f3f3f
28 #define maxm 200001
29 #define mod 998244353
30 //#define LOCAL
31 using namespace std;
32 int read(){
33     int x=0,f=1;char ch=getchar();
34     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
35     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
36     return x*f;
37 }
38 int n,m;
39 int d[maxn];
40 struct QUERY
41 {
42     int l;
43     int r;
44     int data;
45 }q[maxm];
46 bool cmpl(QUERY a,QUERY b){return a.l<b.l;}
47 bool cmpr(QUERY a,QUERY b){if(a.r==b.r) return a.l<b.l;else return a.r<b.r;}
48 int ans[maxm],get[maxn];
49 int main()
50 {
51     std::ios::sync_with_stdio(false);//cout<<setiosflags(ios::fixed)<<setprecision(1)<<y;
52     #ifdef LOCAL
53     freopen("data.in","r",stdin);
54     freopen("data.out","w",stdout);
55     #endif
56     cin>>n;F(i,1,n) cin>>d[i];cin>>m;
57     F(i,1,m){cin>>q[i].l>>q[i].r;q[i].data=i;}
58     int len=sqrt(n);sort(q+1,q+m+1,cmpl);
59     int ll=1,rr=0,cnt=0;
60     while(ll<=m)
61     {
62         rr++;int cur=ll;
63         while(q[ll].l<=rr*len&&ll<=m) ll++;
64         sort(q+cur,q+ll,cmpr);
65         if(rr==len) sort(q+cur,q+m+1,cmpr);
66     }
67     ll=1,rr=0;
68     F(i,1,m){
69         if(q[i].l>ll){
70             F(j,ll,q[i].l-1){
71                 get[d[j]]--;
72                 if(get[d[j]]==0) cnt--;
73             }
74         }
75         else{
76             F(j,q[i].l,ll-1){
77                 get[d[j]]++;
78                 if(get[d[j]]==1) cnt++;
79             }
80         }
81         ll=q[i].l;
82         if(q[i].r<rr){
83             F(j,q[i].r+1,rr){
84                 get[d[j]]--;
85                 if(get[d[j]]==0) cnt--;
86             }
87         }
88         else{
89             F(j,rr+1,q[i].r){
90                 get[d[j]]++;
91                 if(get[d[j]]==1) cnt++;
92             }
93         }
94         rr=q[i].r;
95         ans[q[i].data]=cnt;
96     }
97     F(i,1,m) cout<<ans[i]<<endl;
98     return 0;
99 }

p1972