算法原理：#
对于序列上的查询问题, 如果 $[l, r]$ 的答案可以$O(1)$扩展到$[l - 1, r], [l + 1, r], [l, r - 1], [l, r + 1]$, 那么对于所有询问, 离线处理后可以在$n\sqrt{q}$的时间内找到所有问题的答案。
莫队擅长处理的问题是这么一类问题：区间 $[l, r]$ 中有多少个二元组 $(i, j)$ 满足条件，常规的做法是将区间子区间问题通过前缀和差分的形式转会为区间二元组的问题，这个技巧会经常用到。
具体实现：#
对于区间$[l,r]$, 以$l$所在块的编号为第一关键字升序, $r$为第二关键字排序升序。
优化: 若$l$所在块编号为奇数, 则按$r$为第二关键字升序, 反正则按降序。
具体实现见例题, 主要是编写$O(1)$扩展部分的代码
例题:#
题目大意:
对于给定数列$a$, 每次询问一个区间$[l, r]$, 区间的值是每个数字出现的次数的平方乘这个数本身的和,即$\sum k_s^2 \times s$。
这个问题可以被转化为一个区间二元组的问题，即：
$$
\sum_{l \leq i, j \leq r} a_i[a_i = a_j]
$$
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
| int main () {
ios::sync_with_stdio(0), cin.tie(0);
int n, t;
cin >> n >> t;
vector<int> a(n);
int B = sqrt(n);
for(int i = 0; i < n; i ++) {
cin >> a[i];
}
struct query {
int l, r, id;
};
vector<query> q(t);
for(int i = 0; i < t; i ++) {
auto &[l, r, id] = q[i];
cin >> l >> r;
l --, r --;
id = i;
}
sort(q.begin(), q.end(), [&] (query a, query b) {
if(a.l / B != b.l / B) return a.l < b.l;
return (a.l / B) & 1 ? a.r < b.r : a.r > b.r;
});
ll res = 0;
vector<ll> ans(t);
vector<int> cnt(MAXN);
for(int i = 0, lt = 0, rt = -1; i < t; i ++) {
auto &[l, r, id] = q[i];
while (rt < r) {
int x = a[++ rt];
ll fi = 1ll * cnt[x] * cnt[x] * x;
cnt[x] ++;
ll se = 1ll * cnt[x] * cnt[x] * x;
res = res - fi + se;
}
while(rt > r) {
int x = a[rt --];
ll fi = 1ll * cnt[x] * cnt[x] * x;
cnt[x] --;
ll se = 1ll * cnt[x] * cnt[x] * x;
res = res - fi + se;
}
while(lt < l) {
int x = a[lt ++];
ll fi = 1ll * cnt[x] * cnt[x] * x;
cnt[x] --;
ll se = 1ll * cnt[x] * cnt[x] * x;
res = res - fi + se;
}
while(lt > l) {
int x = a[-- lt];
ll fi = 1ll * cnt[x] * cnt[x] * x;
cnt[x] ++;
ll se = 1ll * cnt[x] * cnt[x] * x;
res = res - fi + se;
}
ans[id] = res;
}
for(ll i : ans) {
cout << i << '\n';
}
}
|
题目大意
$q$ 次询问，每次询问 $[l, r]$ 求有其中有多少个子区间满足区间异或和为 $k$ 。
由于是子区间问题，所以应该需要将此题中的子区间问题化简成为区间二元组的问题，可以通过做前缀和来做此题。
对原数组进行一次前缀异或和操作（新数组记为$s$），那么可以想到满足条件的二元组为
$$
s_r \bigoplus s_{l - 1} = k
$$
维护一个桶记录 $s_i \bigoplus k$ 的数量就可以用莫队解决这个问题。
参考代码
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
| struct qry {
int l, r, id;
};
const int INF = 1e9 + 7, MAXN = 2e5 + 10, mod = 998244353;
int a[MAXN], s[MAXN << 4], cnt[MAXN << 4];
void solve() {
int n, k, m;
cin >> n >> m >> k;
for(int i = 1; i <= n; i ++) {
cin >> a[i];
s[i] = s[i - 1] ^ a[i];
}
vector<qry> q(m);
for(int i = 0; i < m; i ++) {
cin >> q[i].l >> q[i].r;
q[i].id = i;
}
int B = sqrt(n);
sort(q.begin(), q.end(), [&](qry a, qry b) {
int xa = a.l / B, xb = b.l / B;
if(xa != xb) return xa < xb;
int ya = a.r / B , yb = b.r / B;
if(xa & 1) {
return ya > yb;
} else {
return ya < yb;
}
});
vector<ll> res(m);
int lt = 0, rt = -1;
ll w = 0;
for(const auto &[l, r, id] : q) {
while(rt < r) {
rt ++;
int x = s[rt];
w += cnt[x];
cnt[x ^ k] ++;
}
while(rt > r) {
int x = s[rt];
cnt[x ^ k] --;
w -= cnt[x];
rt --;
}
while(lt > l - 1) {
lt --;
int x = s[lt];
w += cnt[x];
cnt[x ^ k] ++;
}
while(lt < l - 1) {
int x = s[lt];
cnt[x ^ k] --;
w -= cnt[x];
lt ++;
}
res[id] = w;
}
for(auto i : res) {
cout << i << "\n";
}
}
|
题目大意
$q$ 次询问，每次询问 $(l_1, r_1, l_2, r_2)$ ，求 $\sum_{x} get(l_1, r_1, x) \times get(l_2, r_2, x)$，其中 $get(l, r, x)$ 表示的区间 $[l, r]$ 中$x$ 出现的次数。
莫队是处理区间二元组的一种手法，而此题中的询问有 $4$ 个参数，我们希望能够通过一些手段转化这个问题。
差分是莫队常见的降低参数个数的手法，将 $get(l, r, x)$ 做一次差分实际上就转化为了 $get(1, r, x) - get(1, l - 1, x)$。
这样原问题就可以化简为
$$
\sum_{x} get(1, r_1, x)get(1, r_2, x) - get(1, r_1, x)get(1, l_2 - 1, x) + get(1, l_1 - 1, x) get(1, l2 - 1, x) - get(1, l_1 - 1, x)get(1, r_2, x)
$$
经此化简，我们将原题转化为了四个不相关的莫队进行求解。
参考代码
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
| const int INF = 1e9 + 7, MAXN = 2e5 + 10, mod = 998244353;
struct qry {
int l, r, id;
};
int a[MAXN], n, m;
void solve() {
cin >> n;
for(int i = 1; i <= n; i ++) {
cin >> a[i];
}
cin >> m;
vector<vector<qry>> q(4, vector<qry> (m));
for(int i = 0; i < m; i ++) {
int l1, r1, l2, r2;
cin >> l1 >> r1 >> l2 >> r2;
q[0][i].l = r1, q[0][i].r = r2, q[0][i].id = i;
q[1][i].l = r1, q[1][i].r = l2 - 1, q[1][i].id = i;
q[2][i].l = l1 - 1, q[2][i].r = l2 - 1, q[2][i].id = i;
q[3][i].l = l1 - 1, q[3][i].r = r2, q[3][i].id = i;
for(int j = 0; j < 4; j ++) {
if(q[j][i].l > q[j][i].r) {
swap(q[j][i].l, q[j][i].r);
}
}
}
int B = sqrt(n);
vector<ll> res(m);
for(int i = 0; i < 4; i ++) {
sort(q[i].begin(), q[i].end(), [&](qry a, qry b) {
int xa = a.l / B, xb = b.l / B;
if(xa != xb) return xa < xb;
int ya = a.r / B , yb = b.r / B;
if(xa & 1) {
return ya > yb;
} else {
return ya < yb;
}
});
ll w = 0;
int lt = 0, rt = 0;
vector<int> cnt1(n + 1), cnt2(n + 1);
for(const auto &[l, r, id] : q[i]) {
while(rt < r) {
rt ++;
int x = a[rt];
w -= 1ll * cnt1[x] * cnt2[x];
cnt2[x] ++;
w += 1ll * cnt1[x] * cnt2[x];
}
while(rt > r) {
int x = a[rt];
w -= 1ll * cnt1[x] * cnt2[x];
cnt2[x] --;
w += 1ll * cnt1[x] * cnt2[x];
rt --;
}
while(lt < l) {
lt ++;
int x = a[lt];
w -= 1ll * cnt1[x] * cnt2[x];
cnt1[x] ++;
w += 1ll * cnt1[x] * cnt2[x];
}
while(lt > l) {
int x = a[lt];
w -= 1ll * cnt1[x] * cnt2[x];
cnt1[x] --;
w += 1ll * cnt1[x] * cnt2[x];
lt --;
}
if(i & 1) {
res[id] -= w;
} else {
res[id] += w;
}
}
}
for(auto i : res) {
cout << i << "\n";
}
}
|
题目大意
给定一个质数 $p$ 与一个大数 $S$，进行$q$ 次询问，每次询问 $[l, r]$ 中有多少个子串满足 $S[l, r]$ 能够被 $p$ 整除。
首先因为是基于 $10$ 进制的，因此 $2, 5$ 是唯二能够整除 $10$ 的数，所以这两个数需要进行特殊讨论。
因为是子串，所以首先想到的是将字串转化为区间二元组进行计算。因为对于前缀和实际上没有意义，我们维护一个后缀和 $suf$，对于一个区间 $S[l, r]$，实际上 $suf_l - suf_{r + 1} = xxx000…0$，那么区间 $S[l, r]$ 实际上所对应的数字就是 $(suf_l - suf_{r + 1}) / 10^k$，已知 $10$ 不能够被 $p$ 整除，那么有且仅有$suf_l - suf_{r + 1} = 0$ 时满足条件，即 $suf_l = suf_{r + 1}$。接下来用莫队就能解决这个问题。
当 $p = 2\ or\ 5$ 时，实际上仅需考虑末位能够被 $p$ 整除的位置到左端点的个数， 即当 $p = 5$ 时，仅需统计 $xxx5$ 和 $xxx0$ 的个数即可。
参考代码
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
105
106
107
108
109
110
111
112
113
114
| const int INF = 1e9 + 7, MAXN = 2e5 + 10, mod = 998244353;
ll suf[MAXN];
struct qry {
int l, r, id;
};
void solve() {
int p;
string s;
cin >> p >> s;
int n = s.size();
int m;
cin >> m;
vector<qry> q(m);
for(int i = 0; i < m; i ++) {
cin >> q[i].l >> q[i].r;
q[i].l --, q[i].r --;
q[i].id = i;
}
vector<int> temp;
temp.push_back(0);
for(int i = n - 1, d = 1; i >= 0; i --) {
suf[i] = (suf[i + 1] + 1ll * (s[i] - '0') * d) % p;
temp.push_back(suf[i]);
d = 1ll * d * 10 % p;
}
sort(temp.begin(), temp.end());
temp.resize(unique(temp.begin(), temp.end()) - temp.begin());
for(int i = 0; i < n; i ++) {
suf[i] = lower_bound(temp.begin(), temp.end(), suf[i]) - temp.begin();
}
int B = sqrt(n);
vector<ll> res(m);
sort(q.begin(), q.end(), [&](qry a, qry b) {
int xa = a.l / B, xb = b.l / B;
if(xa != xb) return xa < xb;
int ya = a.r / B, yb = b.r / B;
if(xa & 1) return ya > yb;
else return ya < yb;
});
if(p == 2 || p == 5) {
int lt = 0, rt = -1;
int cnt = 0;
ll w = 0;
for(const auto &[l, r, id] : q) {
while(rt < r) {
rt ++;
int x = s[rt] - '0';
if(x % p == 0) {
cnt ++;
w += rt - lt + 1;
}
}
while(rt > r) {
int x = s[rt] - '0';
if(x % p == 0) {
w -= rt - lt + 1;
cnt --;
}
rt --;
}
while(lt > l) {
lt --;
int x = s[lt] - '0';
if(x % p == 0) {
cnt ++;
}
w += cnt;
}
while(lt < l) {
int x = s[lt] - '0';
w -= cnt;
if(x % p == 0) {
cnt --;
}
lt ++;
}
res[id] = w;
}
} else {
int lt = 0, rt = -1;
vector<int> cnt(temp.size());
ll w = 0;
for(const auto &[l, r, id] : q) {
while(rt < r + 1) {
rt ++;
int x = suf[rt];
w += cnt[x];
cnt[x] ++;
}
while(rt > r + 1) {
int x = suf[rt];
cnt[x] --;
w -= cnt[x];
rt --;
}
while(lt > l) {
lt --;
int x = suf[lt];
w += cnt[x];
cnt[x] ++;
}
while(lt < l) {
int x = suf[lt];
cnt[x] --;
w -= cnt[x];
lt ++;
}
res[id] = w;
}
}
for(auto i : res) {
cout << i << '\n';
}
}
|