记笔习学队莫
Yamchip
·
·
算法·理论
广告位
讲的非常好的Manacher入门
前言
莫队=离线+暴力+分块。
普通莫队
P3901 数列找不同
题目描述
现有数列 A_1,A_2,\ldots,A_N，Q 个询问 (L_i,R_i)，询问 A_{L_i} ,A_{L_i+1},\ldots,A_{R_i} 是否互不相同。
对于 100\% 的数据，1 \le N,Q \le 10^5，1 \le A_i \le N，1 \le L_i \le R_i \le N。
暴力
学算法就得先学暴力。
不妨设置两个指针 L，R 指向区间的两个端点，L 向前，扫到 x 就将 cnt_x 加 1，L 向后，扫到 x 就将 cnt_x 加 1，R 同理。
这里拿询问一举例，初始指针 L = 1,R = 0：
$L=1,R=1$ 时，$cnt_1 = 1,ans=1$。
$L=1,R=2$ 时，$cnt_1=1,cnt_2=1,ans=2$。
$L=1,R=3$ 时，$cnt_1=1,cnt_2=1,cnt_3=1,ans=3$。
从上面的图可知，每次指针移动后停留在区间 $[L,R]$ 时，$ans$ 即为区间的答案。
这样每次询问只需要边移动指针，边维护答案就行了。
但是，当询问的区间跨度特别大时，算法就会变成 $O(nq)$。
### 优化
我们可以通过调换区间移动的顺序，来减小复杂度。
我们先把区间变成点 $(L,R)$，放到平面直角坐标系上，观察一下。发现这样我们的区间移动变成了点于点的移动，而且点移动的路径是一个哈密顿路径。
但是哈密顿最短路径问题没有多项式做法，并不可行，有没有一种排序，能使点移动的距离尽量小呢？
莫队算法提出了一种较优的排序方式。
**在 $n,q$ 同阶的情况下**，它将暴力的 $O(n^2)$ 优化成了 $O(n\sqrt n)$。
首先将数组分块（块长 $\sqrt n$），将询问按区间左端点所属的块序号排序，如果块相同，则按右端点排序。
~~不会吧，莫队算法这么少？~~ 正所谓，浓缩的都是精华，这就是莫队算法跑的快的原因。
还是把询问转成点放到平面直角坐标系上，方便理解。下图时暴力和莫队算法排序后的区别。
暴力：
莫队：
可以观察到暴力法的横向移动了 $n$ 次, 纵向移动了 $n^2$ 次，莫队算法横向每次移动至多 $\sqrt n$ 次，所以总共移动了 $n \sqrt n$ 次，纵向移动了 $2n\sqrt n$ 次。
在编码时，还有一个小技巧，奇偶化排序：如图，可以发现每次从一个块到下一个块的时候，$R$ 总是会从一个块的最大值移动到下一个块的最小值，这样就会多跑 $n$ 次。此时，我们只需要将相邻块的排序顺序倒一下，在奇数块使用正向排序，在偶数块使用反向排序，就可以省掉 $n \sqrt n$ 次的移动。
所以最终复杂度就是 $O(n\sqrt n)$。那为什么块长为 $\sqrt n$ 是最优呢？设块长为 $B$，则算法复杂度为 $O(nB + \frac{n^2}{B})$，根据均值不等式，当 $nB = \frac{n^2}{B}$，也就是 $B = \sqrt n$ 时，这个式子取到最小值，为 $n\sqrt n$。
以下是最终的莫队排序。
```cpp
bool cmp(node x, node y)
{
//b[i]存i所处的块
if(b[x.l] != b[y.l])
return x.l < y.l;
if(b[x.l] & 1)
return x.r < y.r;
else
return x.r > y.r;
}
```
---
通过以上的讲解，可以发现莫队的本质就是将纵向幅度为 $n$ 的震荡转化为横向幅度为 $\sqrt n$ 的震荡，从而优化复杂度。
### 参考代码
恭喜你学完了普通莫队。
接下来能学更多莫队了。
---
下面放 [P3901](https://www.luogu.com.cn/problem/P3901) 的代码。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, q, l, r, num, a[N], b[N], cnt[N], ans[N];
struct node
{
int l, r, id;
}s[N];
bool cmp(node x, node y)
{
if(b[x.l] != b[y.l])
return x.l < y.l;
if(b[x.l] & 1)
return x.r < y.r;
else
return x.r > y.r;
}
void add(int k)
{
if(++cnt[a[k]] == 1) num++;
}
void del(int k)
{
if(!--cnt[a[k]]) num--;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> q;
int len = sqrt(n);
for(int i = 1;i <= n;i++)
cin >> a[i], b[i] = (i - 1) / len + 1;
for(int i = 1;i <= q;i++)
cin >> s[i].l >> s[i].r, s[i].id = i;
sort(s + 1, s + q + 1, cmp);
l = 1, r = 0;
for(int i = 1;i <= q;i++)
{
while(s[i].l < l) add(--l);
while(s[i].l > l) del(l++);
while(s[i].r > r) add(++r);
while(s[i].r < r) del(r--);
ans[s[i].id] = (num == s[i].r - s[i].l + 1);
}
for(int i = 1;i <= q;i++)
cout << (ans[i] ? "Yes\n" : "No\n");
return 0;
}
```
## 带修莫队
### [P1903 [国家集训队] 数颜色 / 维护队列](https://www.luogu.com.cn/problem/P1903)
#### 题目描述
墨墨购买了一套 $N$ 支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会向你发布如下指令：
1. $Q\ L\ R$ 代表询问你从第 $L$ 支画笔到第 $R$ 支画笔中共有几种不同颜色的画笔。
2. $R\ P\ C$ 把第 $P$ 支画笔替换为颜色 $C$。
对于所有数据，$n,m \leq 133333$。
---
如果这题没有修改操作，那就是一个普通莫队。于是我们可以改进一下普通莫队。
发现只有两维 $L,R$ 很不好做，因为没法知道询问被修改了几次。所以考虑增加一维 $t$，记录这是第几个修改操作后的询问，在维护答案的时候就可以通过移动这一维来实现修改操作。
同时，借用莫队算法的分块思想，对前两维进行分块，排序第三维。但是如果再拿原来 $\sqrt n$ 的块长来排序，算法就会退化成 $O(nm)$ 的。
下面来说明原因。
设块长为 $B$，那么 $L$ 移动了 $m$ 次，每次最多移动 $B$，总共移动 $mB$ 次，$R$ 移动 $m$ 次，每次最多移动 $B$，总共移动 $mB$ 次，$t$ 在每个块内都要移动，有 $\frac {n^2} {B^2}$ 个块，在每个块内最多要移动 $m$ 次，总共 $\frac {mn^2}{B^2}$ 次。
三维总共移动了 $mB + mB + \frac {mn^2}{B^2}$ 次。
根据均值不等式，最小值为 $mn^{\frac{2}{3}}$。
取等的条件为 $B = \frac{n^2}{B^2}$，即为 $B = n^{\frac{2}{3}}$。
### 参考代码
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 133335, S = 1e6 + 5;
int n, m, res, cnt, tot, a[N], b[N], p[S], ans[N];
struct R
{
int p, c;
}s[N];
struct Q
{
int l, r, t, id;
}q[N];
bool cmp(Q x, Q y)
{
if(b[x.l] != b[y.l]) return b[x.l] < b[y.l];
if(b[x.r] != b[y.r]) return b[x.r] < b[y.r];
return x.t < y.t;
}
void add(int x)
{
if(!p[x]) res++;
p[x]++;
}
void del(int x)
{
p[x]--;
if(!p[x]) res--;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
int len = pow(n, 2.0 / 3.0);
for(int i = 1;i <= n;i++)
cin >> a[i], b[i] = (i - 1) / len + 1;
for(int i = 1;i <= m;i++)
{
char op;
cin >> op;
if(op == 'R')
{
cnt++;
cin >> s[cnt].p >> s[cnt].c;
}else
{
tot++;
cin >> q[tot].l >> q[tot].r;
q[tot].t = cnt;
q[tot].id = tot;
}
}
sort(q + 1, q + tot + 1, cmp);
int l = 1, r = 0, t = 0;
for(int i = 1;i <= tot;i++)
{
while(l > q[i].l) add(a[--l]);
while(l < q[i].l) del(a[l++]);
while(r < q[i].r) add(a[++r]);
while(r > q[i].r) del(a[r--]);
while(t < q[i].t)
{
t++;
if(l <= s[t].p && s[t].p <= r)
{
del(a[s[t].p]);
add(s[t].c);
}
swap(s[t].c, a[s[t].p]);
}
while(t > q[i].t)
{
if(l <= s[t].p && s[t].p <= r)
{
del(a[s[t].p]);
add(s[t].c);
}
swap(s[t].c, a[s[t].p]);
t--;
}
ans[q[i].id] = res;
}
for(int i = 1;i <= tot;i++) cout << ans[i] << "\n";
return 0;
}
```
## 树上莫队
### [SP10707 COT2 - Count on a tree II](https://www.luogu.com.cn/problem/SP10707)
#### 题目描述
- 给定 $n$ 个结点的树，每个结点有一种颜色。
- $m$ 次询问，每次询问给出 $u,v$，回答 $u,v$ 之间的路径上的结点的不同颜色数。
- $1 \leq n \leq 4 \times 10^{4}, 1 \leq m \leq 10^{5}$，颜色是不超过 $2 \times 10^{9}$ 的非负整数。
---
学完了前面的莫队，发现都是在序列上进行的。那么，树上莫队也需要转化成序列做。欧拉序是一种树转序列的好方法。
欧拉序会在一个节点第一次进入和最后一次出时将这个节点加入序列。那这题的样例举例：`1 4 8 8 4 3 7 7 6 6 5 5 3 2 2 1`。
在欧拉序上寻找 $u,v$ 两点间的路径，共有两种情况：
1. $\operatorname{lca}(u,v) = u$ 或 $\operatorname{lca}(u,v) = v$。那么 $u,v$ 路径上的点就为 **欧拉序上两点之间只出现过一次的数**。如 $1,6$ 路径上的点就是 `1 4 8 8 4 3 7 7 6` 这个序列只出现过一次的数：`1 3 6`。
2. $\operatorname{lca}(u,v) \ne u$ 且 $\operatorname{lca}(u,v) \ne v$。此时 $u$ 到 $v$ 的路径上多出了 $\operatorname{lca}(u,v)$，需要加上 $\operatorname{lca}(u,v)$ 这个节点。如 $4,6$ 路径上的点就是 `4 3 7 7 6` 这个序列只出现过一次的数加上 $\operatorname{lca}(u,v)$：`4 1 3 6`。
于是我们就把树上的询问转成了序列上的了。此时就可以使用莫队算法统计 **区间里只出现过一次的节点的颜色数量**。这题序列的长度是 $2n$，所以分块的时候块长要设置为 $\sqrt{2n}$。
### 参考代码
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 4e4 + 5, M = 1e5 + 5;
int n, m, cnt, num, res, l = 1, r;
int fa[N], dep[N], siz[N], son[N], top[N];
int head[N], dfn[N << 1], col[N], x[N], b[N << 1], tot[N], p[N], ans[M], s[N], t[N];
struct Edge
{
int to, next;
}edge[N << 1];
struct query
{
int l, r, id, k;
}q[M];
void add(int u, int v)
{
edge[++cnt].to = v;
edge[cnt].next = head[u];
head[u] = cnt;
}
void dfs1(int u, int f)
{
fa[u] = f;
siz[u] = 1;
dfn[++num] = u;
s[u] = num;
dep[u] = dep[f] + 1;
for(int i = head[u]; i; i = edge[i].next)
{
int v = edge[i].to;
if(v == f) continue;
dfs1(v, u);
siz[u] += siz[v];
if(siz[v] > siz[son[u]] || !son[u])
son[u] = v;
}
dfn[++num] = u;
t[u] = num;
}
void dfs2(int u, int topu)
{
top[u] = topu;
if(!son[u]) return ;
dfs2(son[u], topu);
for(int i = head[u]; i; i = edge[i].next)
{
int v = edge[i].to;
if(v == fa[u] || v == son[u]) continue;
dfs2(v, v);
}
}
int lca(int u, int v)
{
while(top[u] != top[v])
{
if(dep[top[u]] < dep[top[v]]) swap(u, v);
u = fa[top[u]];
}
return dep[u] < dep[v] ? u : v;
}
void add(int x)
{
p[x]++;
if(p[x] == 2)
{
tot[col[x]]--;
if(!tot[col[x]]) res--;
return ;
}
if(!tot[col[x]]) res++;
tot[col[x]]++;
}
void del(int x)
{
p[x]--;
if(p[x] == 1)
{
tot[col[x]]++;
if(tot[col[x]] == 1) res++;
return ;
}
if(tot[col[x]] == 1) res--;
tot[col[x]]--;
}
bool cmp(query x, query y)
{
if(b[x.l] != b[y.l]) return x.l < y.l;
if(b[x.l] & 1) return x.r < y.r;
return x.r > y.r;
}
int main()
{
cin >> n >> m;
for(int i = 1;i <= n;i++)
cin >> col[i], x[i] = col[i];
int len = unique(x + 1, x + n + 1) - x - 1;
sort(x + 1, x + len + 1);
for(int i = 1;i <= n;i++)
{
int k = lower_bound(x + 1, x + len + 1, col[i]) - x;
col[i] = k;
}
for(int i = 1;i < n;i++)
{
int u, v;
cin >> u >> v;
add(u, v);
add(v, u);
}
dfs1(1, 1);
dfs2(1, 1);
len = sqrt(num);
for(int i = 1;i <= num;i++)
b[i] = (i - 1) / len + 1;
for(int i = 1;i <= m;i++)
{
int u, v;
cin >> u >> v;
int k = lca(u, v);
if(k != u && k != v)
{
if(s[u] > t[v]) swap(u, v);
q[i] = {t[u], s[v], i, k};
}else
{
if(s[u] > s[v]) swap(u, v);
q[i] = {s[u], s[v], i, 0};
}
}
sort(q + 1, q + m + 1, cmp);
for(int i = 1;i <= m;i++)
{
while(l < q[i].l) del(dfn[l++]);
while(l > q[i].l) add(dfn[--l]);
while(r < q[i].r) add(dfn[++r]);
while(r > q[i].r) del(dfn[r--]);
if(q[i].k) add(q[i].k);
ans[q[i].id] = res;
if(q[i].k) del(q[i].k);
}
for(int i = 1;i <= m;i++)
cout << ans[i] << "\n";
return 0;
}
```
## 回滚莫队
### [AT_joisc2014_c 歴史の研究](https://www.luogu.com.cn/problem/AT_joisc2014_c)
#### 题目描述
日记中记录了连续 $N$ 天发生的事件，大约每天发生一件。
事件有种类之分。第 $i$ 天发生的事件的种类用一个整数 $X_i
表示，X_i 越大，事件的规模就越大。
JOI 教授决定用如下的方法分析这些日记：
-
选择日记中连续的几天 [L,R] 作为分析的时间段；
-
定义事件 A 的重要度 W_A 为 A\times T_A，其中 T_A 为该事件在区间 [L,R] 中出现的次数。
现在，您需要帮助教授求出所有事件中重要度最大的事件是哪个，并输出其重要度。
对于 100\% 的数据，1\le Q,N\le 10^5，1\le X\le 10^9，1\le L\le R\le N。
可以发现这道题的减操作难以实现，所以考虑只加不减。
先将右端点排序，于是右端点就只需要加操作了。因为排序完，左端点变得没有规律，所以只能重新计算。考虑对左端点分块，一个块一个块的做。先把左右端点在同一个块内的操作，暴力统计了。
那么剩下的询问只剩这样的了。
于是可以将询问左端点到块的右端点这段在每次处理询问时重新计算，执行一次的复杂度为 O(\sqrt n)，执行 n 次为 O(n\sqrt n)。而右端点只增不减，每个块最多只需加 n 次，复杂度共为 O(n\sqrt n) 次。再加上暴力的复杂度 O(n\sqrt n)，回滚莫队的复杂度即为 O(n\sqrt n)。
参考代码
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, m, a[N], b[N], t[N], L[N], R[N], cnt[N];
long long res, ans[N];
struct Q
{
int l, r, id;
}q[N];
bool cmp(Q x, Q y)
{
if(b[x.l] != b[y.l]) return b[x.l] < b[y.l];
return x.r < y.r;
}
void add(int x)
{
cnt[x]++;
res = max(res, 1ll * cnt[x] * t[x]);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for(int i = 1;i <= n;i++)
cin >> a[i], t[i] = a[i];
int siz = unique(t + 1, t + n + 1) - t - 1;
int len = sqrt(n);
sort(t + 1, t + siz + 1);
for(int i = 1;i <= n;i++)
{
int k = lower_bound(t + 1, t + siz + 1, a[i]) - t;
a[i] = k;
b[i] = (i - 1) / len + 1;
}
for(int i = 1;i <= ceil(1.0 * n / len);i++)
{
L[i] = R[i - 1] + 1;
R[i] = min(n, L[i] + len - 1);
}
for(int i = 1;i <= m;i++)
{
cin >> q[i].l >> q[i].r;
q[i].id = i;
}
sort(q + 1, q + m + 1, cmp);
int l, r, p = 1;
for(int i = 1; i <= m; p++)
{
memset(cnt, 0, sizeof cnt);
r = R[p];
res = 0;
while(b[q[i].l] == p)
{
l = R[p] + 1;
if(b[q[i].l] == b[q[i].r])
{
long long sum = 0;
for(int j = q[i].l;j <= q[i].r;j++)
cnt[a[j]]++;
for(int j = q[i].l;j <= q[i].r;j++)
sum = max(sum, 1ll * cnt[a[j]] * t[a[j]]);
memset(cnt, 0, sizeof cnt);
ans[q[i].id] = sum;
i++;
continue;
}
while(r < q[i].r) add(a[++r]);
long long tmp = res;
while(l > q[i].l) add(a[--l]);
ans[q[i].id] = res;
while(l <= R[p]) cnt[a[l++]]--;
res = tmp;
i++;
}
}
for(int i = 1;i <= m;i++)
cout << ans[i] << "\n";
return 0;
}