题目描述
$HH$有一串由各种漂亮的贝壳组成的项链。$HH$ 相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。$HH$ 不断地收集新的贝壳，因此，他的项链变得越来越长。
有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答…… 因为项链实在是太长了。于是，他只好求助睿智的你，来解决这个问题。
输入格式
一行一个正整数 $n$，表示项链长度。
第二行 $n$ 个正整数 $a_i$，表示项链中第 $i$ 个贝壳的种类。
第三行一个整数 $m$，表示 $HH$ 询问的个数。
接下来 $m$ 行，每行两个整数 $l,r$，表示询问的区间。
输出格式
输出 $m$ 行，每行一个整数，依次表示询问对应的答案。
样例输入 #1
1
2
3
4
5
6
| 6
1 2 3 4 3 5
3
1 2
3 5
2 6
|
样例输出 #1
提示
【数据范围】
对于 $20%$ 的数据，$1\le n,m\leq 5000$；
对于 $40%$ 的数据，$1\le n,m\leq 10^5$；
对于 $60%$ 的数据，$1\le n,m\leq 5\times 10^5$；
对于 $100%$ 的数据，$1\le n,m,a_i \leq 10^6$，$1\le l \le r \le n$。
本题可能需要较快的读入方式，最大数据点读入数据约 20MB
一、暴力算法
直接暴力枚举询问，然后再枚举区间，这样是$O(n^2)$的
优化
如果说询问是按照左端点递增和右端点递增的，
那么就可以离线排序，用线性的时间扫过去所有询问，用哈希表记录一下就行，同时记录答案。
但是两个端点不能同时递增的，最多保证一个递增。
二、莫队算法
把询问的左端点按照分块的思想分成$\sqrt{n}$块，然后每一块里面的询问$[l,r]$按照右端点递增排序。
在块中：询问区间的右端点是递增的，但是区间的左端点不是递增的；
在块间：左端点是递增的，而右端点不是递增的**(这样就需要指针的移动和回滚，才有了下面的奇偶优化)**。
定义两个指针$tt$(向$r$靠齐)，$hh$(向$l$靠齐)，
然后开始遍历排好序的询问，枚举每个询问$[l,r]$，移动$hh$，$tt$，分别向$l$，$r$靠齐，
同时用一个哈希表记录一下数字出现的个数，同时更新答案即可。
时间复杂度分析
原序列被分成$\sqrt{n}$块，每块长度是$\sqrt{n}$，每块中的询问按照询问右端点递增排序。
那么：
$tt$(向$r$靠齐)指针在每一块中，最坏可能移动$n$次，有$\sqrt{n}$块，所以是$O(n\sqrt{n})$。
$hh$(向$l$靠齐)指针如果在块中移动，最多移动$\sqrt{n}$次。在块间，则最多移动2$\sqrt{n}$次(从这一块的头移动到下一块的尾)。
最终，双指针时间复杂度取最大值，即为$O(n\sqrt{n})$。
奇偶优化
由于每一块中右端点是按从小到大排序的，所以每一块在滚$i$指针时。
滚到最后大概率会滚到整个序列的末尾，然后处理下一块时，右端点$r$又是从小到大排的。
所以$i$得从后面滚回来前面这个$r$，这样就浪费了时间。
如果按奇数块右端点递增排序,偶数块右端点递减排序。
那么指针$i$滚到末尾，然后下一块又是递减排序的话，则可以直接开始滚了，不用滚回来再从新开始。
三、完整代码
时间复杂度：$O(M\sqrt{N})$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
| #include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int N = 1000010, M = 1000010, K = 1000010;
struct query {
int id, l, r;
} q[M];
int n, m;
int a[N];
int cnt[K], len;
int res[M];
int get(int x)
{
return x / len;
}
void add(int x, int& ans)
{
if(cnt[x] == 0) ans ++;
cnt[x] ++;
}
void del(int x, int& ans)
{
cnt[x] --;
if(cnt[x] == 0) ans --;
}
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
scanf("%d", &m);
for(int i = 0; i < m; i ++)
{
int l, r;
scanf("%d%d", &l, &r);
q[i] = {i, l, r};
}
len = sqrt(n);
sort(q, q + m, [&](const query& x, const query& y) {
int i = get(x.l), j = get(y.l);
if(i == j)
{
if(i & 1) return x.r < y.r;
else return y.r < x.r;
}
return i < j;
});
int sum = 0;
for(int k = 0, tt = 0, hh = 1; k < m; k ++)
{
int id = q[k].id, l = q[k].l, r = q[k].r;
while(tt < r) add(a[++ tt], sum);
while(tt > r) del(a[tt --], sum);
while(hh < l) del(a[hh ++], sum);
while(hh > l) add(a[-- hh], sum);
res[id] = sum;
}
for(int i = 0; i < m; i ++) printf("%d\n", res[i]);
return 0;
}
|
四、树状数组（正解）
时间复杂度：$O(MlogN)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
| #include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 1000010, M = 1000010, K = 1000010;
int tr[N];
int n, m;
int a[N], last[K];
int res[M];
struct Query {
int id, l, r;
bool operator< (const Query &x) { return r < x.r; }
} q[M];
int lowbit(int x)
{
return x & -x;
}
void add(int x, int val)
{
for(int i = x; i <= n; i += lowbit(i)) tr[i] += val;
}
int query(int x)
{
int res = 0;
for(int i = x; i; i -= lowbit(i)) res += tr[i];
return res;
}
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
scanf("%d", &m);
for(int i = 0; i < m; i ++)
{
int l, r;
scanf("%d%d", &l, &r);
q[i] = {i, l, r};
}
sort(q, q + m);
for(int i = 1, j = 0; i <= n; i ++)
{
if(last[a[i]]) add(last[a[i]], -1);
add(i, 1);
while(j < m && q[j].r == i)
{
int id = q[j].id, l = q[j].l;
res[id] = query(i) - query(l - 1);
j ++;
}
last[a[i]] = i;
}
for(int i = 0; i < m; i ++) printf("%d\n", res[i]);
return 0;
}
|