莫队
概述
莫队算法主要是用于离线解决通常不带修改只有查询的一类区间问题。如果从\([l,r]\)的答案能够\(O(1)\)拓展到\([l-1,r],[l+1,r],[l,r+1],[l,r-1]\)（即与\([l,r]\)相邻的区间）的答案，那么就可以\(O(n\sqrt
n)\)的复杂度内求出所有询问的答案。
实现
离线后排序，顺序处理每个询问\([l,r]\)，暴力从上一个区间转移到下一个区间答案（一步一步移动即可）。但是我们这样朴素写可能被卡掉，因为他可能类似于
\((1,1),(2,10000),(3,1),(4,10000)\)
那怎么办呢，我们根据\(l\)分块！如果块号一样我们按\(r\)排序，否则我们就比较\(l\)，这样保证每个块的\(r\)最多移动\(N\)，同样的我们同一个块中相邻的两个询问\(l\)最多移动\(\sqrt N\)。这样综合起来时间复杂度就是\(O(N\sqrt N)\)啦。
下面我们看一道ABC莫队板子题
给你\(N(1\le N \le
10^5)\)个数，每个数\(A_i\)大小从\([1,N]\)，给定很多询问，你需要计算
\[\sum\limits_{c_i}{\lfloor
c_i/2\rfloor}\]
其中\(c_i\)是这个区间某个数出现的次数，注意这个maxn一定要取\(\max{(N,Q)}\)
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
| #include <iostream>
#include <map>
#include <vector>
#include <cmath>
#include <algorithm>
#include <array>
using namespace std;
const int maxn = 1e6 + 5;
int N;
int A[maxn];
int cnt[maxn];
namespace MD
{
int ANS[maxn];
int cur_ans;
int len;
bool cmp(array<int, 3> a1, array<int, 3> a2)
{
auto [l, r, id] = a1;
auto [l2, r2, id2] = a2;
if (l / len != l2 / len)
return l < l2;
return r < r2;
}
void inc(int x)
{
cur_ans -= cnt[A[x]] / 2;
cnt[A[x]]++;
cur_ans += cnt[A[x]] / 2;
}
void dec(int x)
{
cur_ans -= cnt[A[x]] / 2;
cnt[A[x]]--;
cur_ans += cnt[A[x]] / 2;
}
void solve(vector<array<int, 3>> &qs, int n)
{
len = sqrt(n);
int L = 1, R = 0;
sort(qs.begin(), qs.end(), cmp);
for (int i = 0; i < qs.size(); i++)
{
auto [l, r, id] = qs[i];
while (L > l) inc(--L);
while (L < l) dec(L++);
while (R < r) inc(++R);
while (R > r) dec(R--);
ANS[id] = cur_ans;
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> N;
for (int i = 1; i <= N; i++)
cin >> A[i];
int Q;
cin >> Q;
vector<array<int, 3>> qs;
for (int i = 1; i <= Q; i++)
{
int l, r;
cin >> l >> r;
qs.push_back({l, r, i});
}
MD::solve(qs, N);
for (int i = 1; i <= Q; i++)
cout << MD::ANS[i] << "\n";
return 0;
}
|