给定一个长度为 $n$ 的正整数序列 $A$ ,有 $m$ 次询问在 $[l,r]$ 区间内有多少个不同的数。
链接
Luogu P1972
题解
这道题目前我只会两种离线的做法。
做法一：莫队
其实做这道题的时候我是不会莫队了。但现在会了，又想写篇莫队的笔记，所以我把这篇题解写出来了。
首先对序列分块，以查询的左端点所在块的序号为第一关键字，右端点的位置为第二关键字排序，然后暴力转移。
时间复杂度： $O((m+n) \sqrt{n})$ 或者简单点： $O(n^\frac{3}{2})$
代码见最后。
做法二：离散化+树状数组
注意到，我们最重要的需要处理的就是重复的问题。如果不需要处理重复的问题，那么就可以直接用树状数组或者前缀和出解了。所以我们考虑到这样一个事情，能否使用某些玄学高端操作，使得我们不需要考虑重复的问题呢？
可以发现，如果一个数已经出现，那么我们就不需要考虑这个数在其他位置上的出现。因此我们有如下的思路：
把查询按照查询的右端点位置从小到大排序。为了发现某个数是否会在我们的查询的序列中出现，我们需要记录这个数最后一次在序列中出现的位置。如果查询区间的左端点在这个数的位置以左，那么查询区间内一定有这个数；而在这个数以右的话，查询区间里一定没有这个数。由于这个数出现多少次我们都只能算一次，所以这个最后出现的数就是我们判断是否含有这个数的依据。
所以我们在树状数组中只给每个数最后出现的这一位赋值 $1$ ,其余的由于上述，不能计入个数，值也就是 $0$ 。这样操作就满足了区间可减性，然后直接树状数组前缀和相减就可以得到每次的结果。
由于数字的范围较大，应该需要离散化。但由于这个跟时间复杂度关系不大，只与空间复杂度有关，所以我就没有这么写。
时间复杂度：$O((m+n) \log{n})$ 或者大体来说 $O(n \log{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
| #include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
struct Query{
int id,l,r;
}query[201000];
int times[1001000],res[201000],num[51000];
int n,m,q;
bool cmp(Query a,Query b){
if(a.l/q!=b.l/q)
return a.l/q<b.l/q;
else
return a.r<b.r;
}
int main(){
scanf("%d",&n);
q = sqrt(n);//q是分块大小
for(int i = 1;i<=n;i++)
scanf("%d",&num[i]);
scanf("%d",&m);
for(int i = 0;i<m;i++){
scanf("%d %d",&query[i].l,&query[i].r);
query[i].id = i;
}
sort(query,query+m,cmp);//排序
int l = 1,r = 1;
int ans = 1;times[num[1]]++;
for(int i = 0;i<m;i++){
int ql = query[i].l,qr = query[i].r;
//转移时先扩大再缩小
while(ql<l){
l--;
if(times[num[l]]++ == 0) ans++;
}
while(r<qr){
r++;
if(times[num[r]]++ == 0) ans++;
}
while(l<ql){
if(--times[num[l]] == 0) ans--;
l++;
}
while(qr<r){
if(--times[num[r]] == 0) ans--;
r--;
}
res[query[i].id] = ans;
}
for(int i = 0;i<m;i++)
printf("%d\n",res[i]);
return 0;
}
|
离散化+树状数组代码：
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
| #include <cstdio>
#include <algorithm>
using namespace std;
inline int lowbit(int x){
return x&(-x);
}
int n,m,num[51000],ans[201000],last[1001000];
int tree[201000];
struct que{
int id,l,r,res;
}qq[1000000];
bool cmp(que a,que b){
if(a.r!=b.r)
return a.r<b.r;
return a.l<b.l;
}
inline void insert(int nown,int val){
for(int i = nown;i<=n;i+=lowbit(i))
tree[i]+=val;
}
inline int query(int nown){
int res = 0;
for(int i = nown;i>0;i-=lowbit(i))
res += tree[i];
return res;
}
int main(){
scanf("%d",&n);
for(int i = 1;i<=n;i++)
scanf("%d",&num[i]);
scanf("%d",&m);
for(int i = 0;i<m;i++){
scanf("%d %d",&qq[i].l,&qq[i].r);
qq[i].id = i;
}
sort(qq,qq+m,cmp);
int end = 0;
for(int i = 0;i<m;i++){
while(end<qq[i].r){//更新last&树状数组
end++;
if(last[num[end]]!=0)//原来出现过就抹去last位置的数
insert(last[num[end]],-1);
insert(end,1);//树状数组加入新标记
last[num[end]] = end;//更新last值
}
ans[qq[i].id] = query(qq[i].r) - query(qq[i].l-1);
}
for(int i = 0;i<m;i++)
printf("%d\n",ans[i]);
return 0;
}
|
