传送门：https://www.luogu.org/problemnew/show/P1972
离线的题目，并且是求区间问题。我们就离线树状数组吧。
线段树也是可以的，这题莫队70分，分块是和莫队一样的，就没写，估计也就70分。
我们来分析一下这个题目吧。
询问一段区间的种类数，并且没有更新操作。我们就分析一下怎么离线。
...
(五分钟后)
好了，经过分析可知，我们按询问区间的右端点排序，这样，所有询问，我们可以for一遍处理出该区间的信息。
(因为对于所有询问，每一个询问都是从左往右的嘛)。然后在每一个询问区间里面，我们都保留尽量靠右的数字，因为左边出现过的在右边也出现了，我们就把左边出现的直接舍掉就可以了。
然后我们保留一下这个询问区间的答案就完事了。
复制代码
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#include <bits/stdc++.h> using namespace std; const int maxn = 1e6+7; int sump[maxn],psum[maxn]; int a[maxn]; int vis[maxn]; int ans[maxn]; int n; struct node { int l; int r; int id; }q[maxn]; bool cmp(node a,node b) { return a.r<b.r; } void add(int p,int x) { for(int i=p;i<=n;i+=(i & -i)) { sump[i] += x; psum[i] += x*p; } } void add_range(int l,int r,int x) { add(l,x); add(r+1,-x); } int query(int p) { int ans = 0; for(int i=p;i;i-=(i & -i)) { ans += sump[i]*(p+1)-psum[i]; } return ans; } int query_range(int l,int r) { return query(r)-query(l-1); } int main() { int T; cin>>T; while(T--) { memset(vis,0,sizeof(vis)); memset(sump,0,sizeof(sump)); memset(psum,0,sizeof(psum)); memset(ans,0,sizeof(ans)); int k; scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) { scanf("%d",a+i); } for(int i=1;i<=k;i++) { scanf("%d%d",&q[i].l,&q[i].r); q[i].id = i; } sort(q+1,q+1+k,cmp); int l = 1; for(int i=1;i<=k;i++) { for(int j=l;j<=q[i].r;j++) { if(!vis[a[j]]) { vis[a[j]] = j; add_range(j,j,1); } else { add_range(vis[a[j]],vis[a[j]],-1); add_range(j,j,1); vis[a[j]] = j; } } l = q[i].r+1; ans[q[i].id] = query_range(q[i].l,q[i].r); } for(int i=1;i<=k;i++) { printf("%dn",ans[i]); } } return 0; }
下面是70分的莫队
复制代码
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#include <bits/stdc++.h> using namespace std; const int maxn = 1e6+7; int cnt[maxn]; int a[maxn]; int pos[maxn]; int ans[maxn]; int Ans = 0; struct node { int l; int r; int id; }q[maxn]; bool cmp(node a,node b) { if(pos[a.l]==pos[b.l]) { return a.r<b.r; } return pos[a.l]<pos[b.l]; } void add(int x) { cnt[a[x]]++; if(cnt[a[x]]==1) { Ans++; } } void del(int x) { cnt[a[x]]--; if(cnt[a[x]]==0) { Ans--; } } int main() { int n,m; scanf("%d",&n); int block = sqrt(n); for(register int i=1;i<=n;i++) { scanf("%d",a+i); } scanf("%d",&m); for(register int i=1;i<=m;i++) { scanf("%d%d",&q[i].l,&q[i].r); q[i].id = i; } sort(q+1,q+1+m,cmp); int L = 0; int R = 0; for(register int i=1;i<=m;i++) { while(q[i].l<L) { L--; add(L); } while(q[i].l>L) { del(L); L++; } while(q[i].r<R) { del(R); R--; } while(q[i].r>R) { R++; add(R); } ans[q[i].id] = Ans; } for(register int i=1;i<=m;i++) { printf("%dn",ans[i]); } return 0; }
最后
以上就是飞快学姐最近收集整理的关于离线树状数组【洛谷P1972】的全部内容，更多相关离线树状数组【洛谷P1972】内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复