Problem Statement
HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH 不断地收集新的贝壳，因此，他的项链变得越来越长。
有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答…… 因为项链实在是太长了。于是，他只好求助睿智的你，来解决这个问题。
一行一个正整数 $n$，表示项链长度。
第二行 $n$ 个正整数 $a_i$，表示项链中第 $i$ 个贝壳的种类。
第三行一个整数 $m$，表示 HH 询问的个数。
接下来 $m$ 行，每行两个整数 $l,r$，表示询问的区间。
Output
输出 $m$ 行，每行一个整数，依次表示询问对应的答案。
1
2
3
4
5
6
|
6
1 2 3 4 3 5
3
1 2
3 5
2 6
|
Sample Output
Constraints
对于 $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
Solving
本题要求对于给定的项链，计算每次询问的区间内包含多少种不同的贝壳。由于需要处理多个询问，且项链长度和询问数量可能较大，直接暴力求解会超时，因此我们可以采用离线操作结合树状数组的方法来解决这个问题。
离线操作
在算法中，操作可以分为在线操作和离线操作。在线操作意味着我们需要实时处理每一个输入，处理完一个输入后才能接着处理下一个输入，并且每个输入的处理结果会立即输出。而离线操作则是先将所有的输入数据全部读入，然后对这些数据进行一定的预处理或者排序等操作，最后再统一处理并输出结果。 在本题中，使用离线操作的好处在于我们可以对所有的询问按照右边界进行排序。这样做的目的是，当我们从左到右遍历项链时，对于每个询问的右边界，我们可以逐步更新树状数组，并且可以避免重复计算。如果不使用离线操作，每次询问都需要从头开始遍历区间，时间复杂度会非常高。
实现思想
本题的核心思路是使用树状数组（Binary Indexed Tree，BIT）来维护每个贝壳种类的右边界信息，通过离线处理询问来提高效率。具体步骤如下：
-
数据读入： - 首先读入项链的长度 n，并依次读入每个位置的贝壳种类，存储在数组 a 中。 - 接着读入询问的个数 m，并将每个询问的左右边界以及询问的编号存储在结构体数组 query 中
-
询问排序： - 对 query 数组按照右边界 r 进行升序排序。这样做的好处是，我们可以按顺序处理询问，从左到右逐步更新树状数组，避免重复计算。
-
树状数组维护： - 定义一个树状数组 bit，用于维护每个位置的贝壳种类的右边界信息。树状数组的主要操作包括 add 和 sum，add 用于更新某个位置的值，sum 用于计算某个区间的和。 - 定义一个数组 mp，用于记录每个贝壳种类的最新右边界位置。
-
处理询问： - 遍历排序后的询问数组，对于每个询问的右边界 r，从左到右遍历到 r 的位置。 - 对于每个位置的贝壳种类 cate，如果该种类之前已经有右边界（即 mp[cate] != 0），则在树状数组中删除之前的右边界（即 bit.add(mp[cate], -1)）。 - 然后更新该种类的右边界为当前位置 s，并在树状数组中更新该位置的值（即 bit.add(s, 1)），同时更新 mp[cate] = s。 - 最后，对于当前询问的左边界 l 和右边界 r，使用树状数组的 rangesum 函数计算该区间内的不同贝壳种类数，并将结果存储在 ans 数组中。
-
输出结果： - 由于我们对询问进行了排序，为了按照原始询问的顺序输出结果，我们根据询问的编号 i 从 ans 数组中取出结果并输出。
代码实现:
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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
|
#include <bits/stdc++.h>
//#define int long long
#define endl '\n'
using namespace std;
using ll = long long;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int N = 1e6+10;
const int M = 0;
int t;
struct BIT
{
ll tree[N];//不要忘记初始化N
int n;
BIT()
{
memset(tree,0,sizeof(tree));
}
//注意树状数组的下标一定从1开始
int lowbit(int i)
{
return i & -i;
}
void add(int i,int v)
{
while(i <= n)
{
//将起始i二进制位不断加其本身最右边的1更新树状数组
tree[i] += v;
i += lowbit(i);
}
}
//返回1-i范围的累加和
ll sum(int i)
{
ll ans = 0;
while(i>0)
{
ans += tree[i];//不断加减去二进制最右边1的数
i -= lowbit(i);//不断减去二进制位最右边的1
}
return ans;
}
//返回l-r范围的累加和
ll rangesum(int l,int r)
{
return sum(r) - sum(l-1);
}
};
struct Query
{
int l,r,i;
}query[N];
bool cmp(Query a,Query b)
{
return a.r < b.r;
}
int a[N],ans[N],mp[N];
signed main()
{
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
int n;
cin >> n;
BIT bit;
bit.n = n;
for(int i=1;i<=n;i++)
{
cin >> a[i];
}
int m;
cin >> m;
for(int i=1;i<=m;i++)
{
int l,r;
cin >> l >> r;
query[i].l = l;//查询的左边界
query[i].r = r;//查询的右边界
query[i].i = i;//查询的编号，用于存入查询后的答案数组
}
sort(query+1,query+1+m,cmp);//以右边界大小升序排序
for(int q=1,s=1;q<=m;q++)//s指针一直向右移动，只需初始化为1一次否则会TLE
{
int r = query[q].r;
for(;s<=r;s++)
{
int cate = a[s];//s指针不断向右边界靠拢
if(mp[cate]!=0)//如果当前贝壳种类已有右边界
{
bit.add(mp[cate],-1);//则删除之前的右边界
}
bit.add(s,1);//更新当前种类的右边界至当前位置
mp[cate] = s;//此时cate这个种类的右边界在s指针处
}
int l = query[q].l;
int i = query[q].i;
ans[i] = bit.rangesum(l,r);//利用树状数组范围求和求出此范围里有多少右边界（即有多少种类的贝壳）并存入当前询问编号下的答案数组中
}
for(int i=1;i<=m;i++)
{
cout << ans[i] << endl;//由于是离线操作，按照查询顺序输出答案
}
return 0;
}
|
通过上述的离线操作和树状数组的使用，我们可以在 $O((n + m) \log n)$ 的时间复杂度内解决这个问题。