概念
莫队算法是由莫涛提出的算法,可以解决一类离线区间询问问题,适用性极为广泛。同时将其加以扩展,便能轻松处理树上路径询问以及支持修改操作。
假设 \(n=m\) ,对于序列上的区间询问问题,如果得知 \([l,r]\) 的答案,可以在 \(O(1)\) 的时间推算出 \([l-1,r],[l+1,r],[l,r-1],[l,r+1]\) 的答案,那么我们就可以在 \(O(n\sqrt{n})\) 的时间求出所有询问的答案。
实现
将所有的询问离线后以左端点所在的块为第一关键字,右端点为第二关键字进行排序。按排序后的顺序处理每一个询问,暴力从上一个区间的答案推出当前区间的答案。
核心代码:
for (int i = 1; i <= m; ++i) {
while (l < q[i].l)
Del(l++);
while (l > q[i].l)
Add(--l);
while (r < q[i].r)
Add(++r);
while (r > q[i].r)
Del(r--);
ans[q[i].AnsId] = res;
}
优化
在很多时候,我们不能盲目的将块长设置为 \(\sqrt{n}\) ,如果遇到 \(m\) 和 \(\sqrt{n}\) 同阶时,我们就有可能被构造出的数据卡掉。在随机数据下,块长设为 \(\dfrac{n}{\sqrt{\dfrac{2}{3}m}}\) 会快一些。
我们发现,莫队算法实际上看上去仅仅是暴力的优化。但是为什么使用这种看似暴力的做法却可以通过高难度的题目呢?很显然,我们的时间复杂度在排序时被优化了。所以,排序节省了我们很多的时间。
于是又有了一种新的排序方法:奇偶性排序。
我们在选择奇数块时,按照右端点从小到大排序,在偶数块时从大到小排序,这样可以减少右端点进行大跳动的次数。
而为什么这样排序会快呢?是因为右指针移动到右边后就不需要跳回左边了,而跳回左边后处理下一个块是要跳动到右边的。很明显,这样就会优化近一半的时间复杂度。
代码:
inline bool operator < (const Query &y) const {
return BlockId == y.BlockId ? (BlockId & 1 ? r<y.r : r>y.r) : l < y.l;
}
应用
SP3267 DQUERY - D-query
Description:求区间有多少不同的数字
Solution:我们在设计 Add 函数和 Del 函数时,其实很好设计。因为 \(a_i\) 的值域只有 \(10^6\) ,所以我们开个桶记录,每次这个数的数量都加上或减去一即可。
Code:
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e6 + 7, M = 1e6 + 7;
struct Query {
int l, r;
int AnsId, BlockId; // AnsId 表示时第几次询问,BlockId 表示第几块
inline bool operator < (const Query y) const {
return BlockId == y.BlockId ? (BlockId & 1 ? r<y.r : r>y.r) : l < y.l; // 奇偶性优化
}
} q[M];
int a[N];
int ans[M];
int cnt[N]; // 桶
int n, m;
int block;
int l = 1, r = 0, res;
inline void Add(int x) {
++cnt[a[x]];
if (cnt[a[x]] == 1)
++res;
}
inline void Del(int x) {
--cnt[a[x]];
if (!cnt[a[x]])
--res;
}
signed main() {
scanf("%d", &n);
block = n / sqrt((m << 1) / 3);
for (int i = 1; i <= n; ++i)
scanf("%d", a + i);
scanf("%d", &m);
for (int i = 1; i <= m; ++i) {
scanf("%d%d", &q[i].l, &q[i].r);
q[i].AnsId = i;
q[i].BlockId = (q[i].l - 1) / block + 1;
}
sort(q + 1, q + 1 + m);
for (int i = 1; i <= m; ++i) {
while (l < q[i].l)
Del(l++);
while (l > q[i].l)
Add(--l);
while (r < q[i].r)
Add(++r);
while (r > q[i].r)
Del(r--);
ans[q[i].AnsId] = res; // 模板
}
for (int i = 1; i <= m; ++i)
printf("%d\n", ans[i]);
return 0;
}
P2709 小B的询问
Description:求区间每个数字出现次数的平方和
Solution:因为 \(a_i\) 的值域只有 \(5 \times10^4\) ,所以我们开个桶记录每个数出现次数。那么平方和怎么计算呢?
注意到
\[(a+1)^2=a^2+2a+1 \]于是我们就可以很轻松地设计 Add 函数和 Del 函数了。
Code:
#include <cmath>
#include <cstdio>
#include <algorithm>
typedef long long ll;
using namespace std;
const int N = 5e4 + 7;
struct Query {
int l, r;
int AnsId, BlockId;
inline bool operator < (const Query y) const {
return BlockId == y.BlockId ? (BlockId & 1 ? r<y.r : r>y.r) : l < y.l;
}
} q[N];
ll a[N];
ll cnt[N];
ll ans[N];
int n, m, k;
int block, l = 1, r;
ll res;
inline void Add(int x) {
res += (cnt[a[x]] << 1) + 1;
++cnt[a[x]];
}
inline void Del(int x) {
res -= (cnt[a[x]] << 1) - 1;
--cnt[a[x]];
}
signed main() {
scanf("%d%d%d", &n, &m, &k);
block = n / sqrt((m << 1) / 3);
for (int i = 1; i <= n; ++i)
scanf("%lld", a + i);
for (int i = 1; i <= m; ++i) {
scanf("%d%d", &q[i].l, &q[i].r);
q[i].AnsId = i;
q[i].BlockId = (q[i].l - 1) / block + 1;
}
sort(q + 1, q + 1 + m);
for (int i = 1; i <= m; ++i) {
while (l < q[i].l)
Del(l++);
while (l > q[i].l)
Add(--l);
while (r < q[i].r)
Add(++r);
while (r > q[i].r)
Del(r--);
ans[q[i].AnsId] = res;
}
for (int i = 1; i <= m; ++i)
printf("%lld\n", ans[i]);
return 0;
}
P1494 [国家集训队] 小 Z 的袜子
Description:查询区间内选到两数相同的概率
Solution:将题意用式子可以表示为
\[\dfrac{\sum \dfrac{a_k(a_k-1)}{2}}{\dfrac{len(len-1)}{2}} \](其中 \(a_k\) 表示每个数字出现的次数,\(len\) 表示区间长度
将式子化简,可得
\[\dfrac{\sum a_k^2 - \sum a_k}{len(len-1)} \]由 \(a_k\) 的定义可得 \(\sum a_k=len\)
所以原式等价于
\[\dfrac{\sum a_k^2 - len}{len(len-1)} \]那么问题就转化为求区间数字出现次数平方和,按上题思路解决即可
Code:
#include <map>
#include <set>
#include <cmath>
#include <cstdio>
#include <algorithm>
typedef long long ll;
using namespace std;
const int N = 5e4 + 7;
struct Query {
int l, r;
int AnsId, BlockId;
inline bool operator < (const Query y) const {
return BlockId == y.BlockId ? (BlockId & 1 ? r<y.r : r>y.r) : l < y.l;
}
} q[N];
ll a[N];
ll cnt[N];
pair<ll, ll> ans[N];
int n, m;
int block, l = 1, r;
ll res;
inline void Add(int x) {
res += (cnt[a[x]] << 1) + 1;
++cnt[a[x]];
}
inline void Del(int x) {
res -= (cnt[a[x]] << 1) - 1;
--cnt[a[x]];
}
template<class T>
inline T gcd(T gcd_a, T gcd_b) {
while (gcd_b ^= gcd_a ^= gcd_b ^= gcd_a %= gcd_b);
return gcd_a;
}
signed main() {
scanf("%d%d", &n, &m);
block = n / sqrt((m << 1) / 3);
for (int i = 1; i <= n; ++i)
scanf("%lld", a + i);
for (int i = 1; i <= m; ++i) {
scanf("%d%d", &q[i].l, &q[i].r);
q[i].AnsId = i;
q[i].BlockId = (q[i].l - 1) / block + 1;
}
sort(q + 1, q + 1 + m);
for (int i = 1; i <= m; ++i) {
while (l < q[i].l)
Del(l++);
while (l > q[i].l)
Add(--l);
while (r < q[i].r)
Add(++r);
while (r > q[i].r)
Del(r--);
if (q[i].l == q[i].r)
ans[q[i].AnsId] = {0, 1};
else
ans[q[i].AnsId] = {res - (q[i].r - q[i].l + 1), (ll)(q[i].r - q[i].l + 1) *(q[i].r - q[i].l)};
}
for (int i = 1; i <= m; ++i)
if (ans[i].first)
printf("%lld/%lld\n", ans[i].first / gcd(ans[i].first, ans[i].second), ans[i].second / gcd(ans[i].first,
ans[i].second));
else
puts("0/1");
return 0;
}
CF617E XOR and Favorite Number
我们可以先预处理出前缀异或值,由前缀和性质可知,我们的问题就变成了在前缀和数组中有多少对 \(i,j\) 满足 \(a_i \operatorname{xor} a_j = k\),答案为 \(ans(r)-ans(l-1)\) ,为了方便我们存储左端点的时候就将其减一。
注意到
\[x \operatorname{xor} y = k \ \ \ \ \Longrightarrow \ \ \ \ x \operatorname{xor} k = y \]所以每次加入一个数字 \(x\) 后,和 \(x\) 异或后等于 \(k\) 的数字都可以算入答案。也就是说,我们只要知道区间内有多少个数字 \(y\) 满足 $y=x \operatorname{xor} k $,就可以知道答案要加上几。删除时同理。
代码:
#include <cmath>
#include <cstdio>
#include <algorithm>
typedef long long ll;
using namespace std;
const int N = 1e5 + 7, MAX = 2e6 + 7;
struct Query {
int l, r;
int AnsId, BlockId;
inline bool operator < (const Query y) const {
return BlockId == y.BlockId ? (BlockId & 1 ? r<y.r : r>y.r) : l < y.l;
}
} q[N];
ll a[N];
ll cnt[MAX];
ll ans[N];
int n, m, k;
int block, l = 1, r;
ll res;
inline void Add(int x) {
res += cnt[a[x] ^ k];
++cnt[a[x]];
}
inline void Del(int x) {
--cnt[a[x]];
res -= cnt[a[x] ^ k];
}
signed main() {
scanf("%d%d%d", &n, &m, &k);
block = sqrt(n);
for (int i = 1; i <= n; ++i) {
scanf("%lld", a + i);
a[i] ^= a[i - 1]; // 直接赋值为前缀异或数组
}
for (int i = 1; i <= m; ++i) {
scanf("%d%d", &q[i].l, &q[i].r);
--q[i].l;
q[i].AnsId = i;
q[i].BlockId = (q[i].l - 1) / block + 1;
}
sort(q + 1, q + 1 + m);
for (int i = 1; i <= m; ++i) {
while (l < q[i].l)
Del(l++);
while (l > q[i].l)
Add(--l);
while (r < q[i].r)
Add(++r);
while (r > q[i].r)
Del(r--);
ans[q[i].AnsId] = res;
}
for (int i = 1; i <= m; ++i)
printf("%lld\n", ans[i]);
return 0;
}
CF220B Little Elephant and Array
普通莫队操作,Add 和 Del 时判断出现次数是否和其相等即可。
但是值域大到 \(10^9\) ,无法直接用桶存储。
注意到 \(>n\) 的数字都不可能对答案产生贡献,所以我们去掉这些数,这样值域就是 \(10^5\) 的了。
代码:
#include <cmath>
#include <cstdio>
#include <algorithm>
typedef long long ll;
using namespace std;
const int N = 1e5 + 7;
struct Query {
int l, r;
int AnsId, BlockId;
inline bool operator < (const Query y) const {
return BlockId == y.BlockId ? (BlockId & 1 ? r<y.r : r>y.r) : l < y.l;
}
} q[N];
int a[N];
int cnt[N];
int ans[N];
int n, m, k;
int block, l = 1, r;
ll res;
inline void Add(int x) {
if (~a[x]) {
if (cnt[a[x]] == a[x])
--res;
++cnt[a[x]];
if (cnt[a[x]] == a[x])
++res;
}
}
inline void Del(int x) {
if (~a[x]) {
if (cnt[a[x]] == a[x])
--res;
--cnt[a[x]];
if (cnt[a[x]] == a[x])
++res;
}
}
signed main() {
scanf("%d%d", &n, &m);
block = sqrt(n);
for (int i = 1; i <= n; ++i) {
scanf("%d", a + i);
if (a[i] > n)
a[i] = -1;
}
for (int i = 1; i <= m; ++i) {
scanf("%d%d", &q[i].l, &q[i].r);
q[i].AnsId = i;
q[i].BlockId = (q[i].l - 1) / block + 1;
}
sort(q + 1, q + 1 + m);
for (int i = 1; i <= m; ++i) {
while (l < q[i].l)
Del(l++);
while (l > q[i].l)
Add(--l);
while (r < q[i].r)
Add(++r);
while (r > q[i].r)
Del(r--);
ans[q[i].AnsId] = res;
}
for (int i = 1; i <= m; ++i)
printf("%d\n", ans[i]);
return 0;
}
标签:cnt,int,res,BlockId,Add,--,算法,莫队
From: https://www.cnblogs.com/wshcl/p/MoDui.html