Part 0. 目录
- 概念
- 普通莫队
- 树上莫队
- 带修莫队
Part 1. 概念
莫队是由莫涛提出的算法。莫队算法可以解决一类离线区间询问问题，适用性极为广泛。
Part 2. 普通莫队
普通莫队主要针对于多次区间询问的问题，基于分块的思想。
过程如下：
先将当前区间 \([l,r]\) 设为 \([1,0]\)，再每次移动一个端点，即变为 \([l-1,r],[l,r+1],[l+1,r],[l,r-1]\)。也就是说每次移动长度会加 \(1\) 或减 \(1\)，从而会多一个元素或减一个元素，进而我们就产生了两个用于在移动时记录答案的函数 \(\operatorname{add}\) 和 \(\operatorname{del}\)。
调用的代码如下：
inline void add(int x) {
//...
}
inline void del(int x) {
//...
}
sort(q + 1, q + m + 1);
int l = 1, r = 0;
for(int i = 1; i <= m; i++) {
while(l > q[i].l) { add(a[--l]); }
while(r < q[i].r) { add(a[++r]); }
while(l < q[i].l) { del(a[l++]); }
while(r > q[i].r) { del(a[r--]); }
ans[q[i].id] = sum;
}
而排序怎么排以及块长 \(bl\) 取多少就决定了代码的时间复杂度。
一般的排序方式是先按左端点所在块为第一关键字，再按右端点为第二关键字排序，代码如下：
return b[l] != b[x.l] ? l < x.l : r < x.r;
但对于这种：
画框部分就多移动了两遍，于是我们考虑奇偶化排序，也就是若左端点所在块相等，则若为奇数块，则按右端点升序排序；否则按右端点降序排序。
代码如下：
return b[l] != b[x.l] ? l < x.l : (r == x.r ? 0 : (b[l] & 1) ^ (r < x.l));
此时排序情况如下，很明显减少了一倍的移动量。
时间复杂度为 \(\mathcal{O}\left(m(\sqrt{n}+\log_2m)\right)\)。
接着便是一堆例题。
SP3267 & P1972
题目大意：每次询问求区间 \([l,r]\) 内的权值种数。
题目的关键在于 \(\operatorname{add}\) 和 \(\operatorname{del}\) 两个函数。
对于一个数 \(a_i\)，在它刚进入区间 \([l,r]\) 时，那么 \(a_i\) 出现的个数加 \(1\)，若它之前未出现过，代表种数多 \(1\)。
同理，在它刚离开区间 \([l,r]\) 时，\(a_i\) 出现的个数减 \(1\)，若现在其个数为 \(0\)，代表种数少 \(1\)。
两个函数代码如下：
inline void add(int x) { sum += !cnt[x]++; }
inline void del(int x) { sum -= !--cnt[x]; }
PS：P1972 需要卡常，莫队并非正解，但卡的过去。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 5;
int n, m, c[N], bl, b[N], sum = 0, cnt[N], ans[N];
struct node {
int l, r, id;
bool operator < (const node &x) const {
if(b[l] != b[x.l]) { return b[l] < b[x.l]; }
return r < x.r;
}
} a[N];
inline void add(int x) { sum += !cnt[x]++; }
inline void del(int x) { sum -= !--cnt[x]; }
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
bl = sqrt(n + 1);
for(int i = 1; i <= n; i++) {
cin >> c[i];
b[i] = (i - 1) / bl + 1;
}
cin >> m;
for(int i = 1; i <= m; i++) {
cin >> a[i].l >> a[i].r;
a[i].id = i;
}
sort(a + 1, a + m + 1);
int l = 1, r = 0;
for(int i = 1; i <= m; i++) {
while(l > a[i].l) { add(c[--l]); }
while(r < a[i].r) { add(c[++r]); }
while(l < a[i].l) { del(c[l++]); }
while(r > a[i].r) { del(c[r--]); }
ans[a[i].id] = sum;
}
for(int i = 1; i <= m; i++) {
cout << ans[i] << '\n';
}
return 0;
}
P1494
题目链接：link。
题目大意：令区间 \([l,r]\) 内 \(x\) 出现了 \(c_x\) 次，求 \(\dfrac{\sum c_x\times(c_x-1)\div2}{(r-l+1)\times(r-l)\div2}\)。
同样是两个函数，但很好处理，每次 \(sum\) 加或减 \(c_x\) 即可。
P2709
题目链接：link。
题目大意：求 \(\sum {c_x}^2\)。
对于每次移动，\(sum\) 加或减 \((c_x+1)^2-{c_x}^2=2c_x+1\)。
CF1000F
题目链接：link。
题目大意：求任意一个 \(c_x=1\) 的 \(x\)。
用一个栈来存满足条件的 \(x\)。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n, m, a[N], bl, sum = 0, cnt[N], ans[N];
int b[N], c[N], tot;
struct node {
int l, r, b, id;
bool operator < (const node &x) const {
if(b != x.b) { return b < x.b; }
return r == x.r ? 0 : (b & 1) ^ (r < x.r);
}
} q[N];
inline void add(int x) {
++cnt[x];
if(cnt[x] == 1) {
++sum;
b[++tot] = x;
c[x] = tot;
}
if(cnt[x] == 2) {
--sum;
b[c[x]] = b[tot];
c[b[tot]] = c[x];
b[tot--] = c[x] = 0;
}
}
inline void del(int x) {
--cnt[x];
if(cnt[x] == 1) {
++sum;
b[++tot] = x;
c[x] = tot;
}
if(cnt[x] == 0) {
--sum;
b[c[x]] = b[tot];
c[b[tot]] = c[x];
b[tot--] = c[x] = 0;
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
bl = sqrt(n);
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
cin >> m;
for(int i = 1; i <= m; i++) {
cin >> q[i].l >> q[i].r;
q[i].b = q[i].l / bl, q[i].id = i;
}
sort(q + 1, q + m + 1);
int l = 1, r = 0;
for(int i = 1; i <= m; i++) {
while(l > q[i].l) { add(a[--l]); }
while(r < q[i].r) { add(a[++r]); }
while(l < q[i].l) { del(a[l++]); }
while(r > q[i].r) { del(a[r--]); }
if(sum) {
ans[q[i].id] = b[tot];
}
}
for(int i = 1; i <= m; i++) {
cout << ans[i] << '\n';
}
return 0;
}
CF220B
题目链接：link。
题目大意：有多少个 \(x\) 满足 \(c_x=x\)。
对于 \(\operatorname{add}\) 函数，如果 \(c_x\gets c_x+1\) 后 \(c_x=x\)，满足条件，答案加 \(1\)；如果 \(c_x=x+1\)，代表这个 \(x\) 本来满足条件，现在不满足了，答案减 \(1\)。\(\operatorname{del}\) 函数同理。
两个函数代码如下：
inline void add(int x) {
if(x > n) { return ; }
++cnt[x];
if(cnt[x] == x) { ++sum; }
if(cnt[x] == x + 1) { --sum; }
}
inline void del(int x) {
if(x > n) { return ; }
--cnt[x];
if(cnt[x] == x) { ++sum; }
if(cnt[x] == x - 1) { --sum; }
}
Part 3. 树上莫队
对于树上路径问题，通常是用欧拉序转换为线性，还要加上 LCA，所以代码通常会很长。对于子树的问题，通常用 dfn 序转换。
未完。
标签：cnt,int,sum,++,笔记,学习,--,add,莫队 From： https://www.cnblogs.com/cyf1208/p/18018537