莫队算法与根号分治

[[ slider_text ]]

[[ item.c ]]

莫队算法与根号分治

发布时间 2023-05-28 作者：zhangminchen 来源：算法小站

莫队 根号分治

## 莫队算法
### 求区间内有几个相同的数
**问题描述：小Z的袜子**
给你 $$n$$ 个数，$$m$$ 个区间 $$[l, r]$$，在 $$[l, r]$$ 中**随机选两个下标不同的数**
问有多大的概率，使得随机选出的两个数相同

**莫队算法适用场景**
对于**区间**操作，如果**加入一个数或者删除一个数**比较容易操作
合并**区间**却不容易操作，这个时候可以考虑莫队算法，简单来说，用 `cnt[x]` 维护 `x` 出现的次数

当区间加入某个数`x`的时候，那么`ans += cnt[x],  cnt[x]++`，反之，删除某个数时候
`cnt[x]--,  ans -= cnt[x]`

也就是说把 $$O(nm)$$ 个区间查询问题，转换成 $$O(n \sqrt{m})$$ 个**加数和删数**操作
实际上 $$[l, r] \to [l+1, r]$$ 等价于加入一个数或者删除一个数的操作

**莫队算法的思想**
*

离线读入所有的询问，并且将区间按 $$\sqrt{n}$$  分块
  
* 将询问 $$[l, r]$$ 按左端点 $$l$$ 分类，假设左端点都在第一个块中，右端点任意，考虑维护

> 假设现在处理第一个块，那么
   ```bash
   for R in [1, n]
       维护 x in [1, R]，cnt[x]，同时维护 1~R 的其他答案
   有了 [1, R] 的信息之后，假设我们现在要处理 [L, R]
   把左端点从 1 -> L 即可，也就是删除一些数
   ```
   
在实现上也可以简单一点处理，对区间**按左端点排序**
> 假设从 $$[L', R'] \to [L, R]$$，可以先将右端点从$$R' \to R$$
   然后再移动左端点从 $$L' \to L$$
   
**莫队算法的实现**
区间初始化 `l = 1, r = 0`，**先扩大区间，再缩小区间**，直到到达询问区间 `[L, R]`
这样可以防止一些边界错误

* 离线读入所有的询问，假设块的大小是`B`，对每个询问**左端点**，看它在哪个块中
  `l / B` 就是块所在的编号，优先按**块编号大小**排序
  为了让常数更小，如果块编号是奇数，按询问右端点**升序排列**，偶数按右端点**降序排列**
  
*  初始化区间为 `l = 1, r = 0`（莫队下标从 `1` 开始），处理每个询问 `[L, R]`
   先扩大区间，`while (r < R)  r++, add(r)`，同时 `while (l > L)  l--, add(l)`
   然后考虑缩小区间 `while (r > R) del(r), r--`，同时 `while (l < L)  del(l), l++`
   
*  `add(x), del(x)` 函数需要自己实现，注意，`x` 为数组下标

```bash
function<void(int)> add = [&](int x) {
	int val = (int)data[x];
	info += cnt[val];
	cnt[val] += 1;
};

function<void(int)> del = [&](int x) {
	int val = (int)data[x];
	cnt[val] -= 1;
	info -= cnt[val];
};
```
> 特别说明，这里新加入一个**下标** $$x$$，统计 `cnt[ a[x] ]` 的时候，用了组合的意义
  对原来的区间，新加入的数的值是 `val = a[x]`，那么**原区间**中，一共有 `cnt[val]` 个值可以与 `a[x]` **成对**
  所以加入 $$x$$ 对答案的贡献是 `info += cnt[x]`，此时再将 `x` 放入区间中 `cnt[x] += 1`
  
> 删除下标也是如此，但注意的是，你要删除 `x`，`x` 对答案的贡献是多少？
   是区间**除了**$$x$$这个位置之外，还有多少个数和 `a[x]` 值相同？
   需要 `cnt[val] -= 1, info -= cnt[val]`
   
### 莫队算法的封装
```bash
template<class T, int B, int qsz>
T 是维护信息的类型，一般为long long 或是 int
qsz 对应询问的结构，一般应该满足 qsz >= 3，每一个询问对应是 array<int, qsz> qu
举个例子，询问用 {l, r, id, extra_data} 来表示，此时 qsz = 4

构造函数
Mo(maxv, const vector<T>& a, const vector<array<int, qsz> > &q)
maxv 对应值域的大小，因为莫队常常需要统计值出现的次数，cnt[0...maxv]
a 表示原数组
q 是离线后的所有询问

数据结构
vector<T> cnt，莫队统计值出现次数
vector<T> data，原数组的信息
vector<T> ans(que.size())  存储每个询问的答案，数组大小为 que.size()
info  莫队算法中，对某一段查询区间 [ql, qr]，所维护的信息
```

### 莫队算法的应用
询问**区间**某个数**出现多少次**？**恰好出现** $$k$$ 次的数有几个之类的问题
都可以用莫队来解决

给定一个序列 $$a_1, \cdots, a_n$$，给出若干个询问
每次询问 $$[l, r]$$ 恰好出现 $$k$$ 次的数有几个？

**算法分析**
直接莫队，答案 `ans[ freq[...] ]` 表示出现 `freq` 次的数有 `ans[freq]` 个

加入一个下标 $$x$$，对应加入的值为 `val = a[x]`
此时这个数**原来出现了**几次呢？原来出现的次数为 `freq[val]` 次
那么 `cnt[ freq[val] ] -= 1`，这个值对应的**旧频率**，在对这个**旧频率**计数中应该先减掉
同时更新频率， `freq[val]++,  cnt[ freq[val] ] += 1`

> **加入一个数**，先把这个数对应的**旧频率**，先从**频率计数**中删掉
  然后**更新频率**，再把**新频率**加到**频率计数**中

## 根号分治
### 问题一
根号分治可以用来处理**下标取模**有关的问题
**问题描述一**
给定一个序列 $$a_1, \cdots, a_n$$，一开始都是 $$0$$，支持以下操作
*

`1 x y d`，对数组中所有下标 $$i \equiv y (\bmod x)$$ 的位置都加上 $$d$$
  > 即满足 $$y, y+x, y+2x, \cdots, y+kx$$ 的位置
  
*  `2 p`，单点询问 $$a_x$$ 的值

**算法分析**
> 首先看修改操作，$$y, y+x, y+2x \cdots, y+kx, \quad (y+kx \leqslant n)$$

直观地想，对于 $$x$$ **较大**的情况，我们要修改的数比较少，可以直接**暴力**
如果 $$x \geqslant \sqrt{n}$$，那么实际上我们只需要修改 $$n / \sqrt{n} = \sqrt{n}$$ 个数
暴力 `for` 可以在 $$O(\sqrt{n})$$ 的时间复杂度内解决，答案用 `val[p]` 存储
其中 `p` 表示实际上的**下标**

如果 $$x < \sqrt{n}$$ 呢？修改的数会很多，但是 $$x$$ 又不是很大，可以考虑**打标记**
对 $$x$$ 的**余数进行分类**，模$$x$$可能的取值就在 $$[0, x) = [0, \sqrt{n})$$ 之内
具体来说，对 $$\bmod x = y$$，标记 $$\text{tag}(x, y) += d$$ (下标对 $$x$$ 取余为 $$y$$ 的都被修改了)

> 那么对于查询操作呢？查询 $$a_p$$

注意到 $$p = y + kx$$，之前的操作 `1 x y`，$$x$$ 的值有的很大，有的很小

此时 `val[p]` 就对应 $$x$$ 值很大时候的修改结果

* 但是 $$x$$ 的值还可能很小，此时我们需要**暴力检查** $$x$$ 的值可能选取了哪些？
  `for x`，$$x \in [0, \sqrt{n})$$ 检查 $$x$$，而 $$p = y + kx$$
  检查标记 $$\text{tag}(x, p \bmod x)$$ 即可，令 `val[p] += tag[x][p % x]`
  这样我们便把 `x` 较小的那一部分修改也给算上了
  
### 问题二
对于**一般图**的情况，我们在图上进行修改，也没有特别好的 $$O(n\log n)$$ 级别的算法
可以考虑对**点的度数分类**，然后再根号分治

**问题描述**
给定 $$n$$ 个点 $$m$$ 条边的图，每个点一开始都是白色，支持 $$q$$ 个操作
*

`1 x`，翻转 $$x$$ 点的颜色，黑到白，白到黑
   
*  `2 x`，查询 $$x$$ 点周围有多少个黑色邻居

**算法分析**
可以根据**点的度数**分类，设一个 $$O(\sqrt{2m})$$ 级别的阈值 $$T$$
将所有 $$\text{deg} \geqslant T$$ 的点记为**大点**，$$\text{deg} < T$$ 记为**小点**

> 考虑查询操作

如果是小点的话，只需要**暴力**这个点的所有邻居，统计出来即可
大点因为邻居非常多，不能直接暴力，那么考虑**修改的时候维护**
注意到**大点**虽然邻居多，但**大点**一共只有 $$O(2m / T) = O(\sqrt{m})$$ 个

> 怎么一边修改一边维护呢？

对于**所有的点** $$x$$ ，要用 `bigv(x)` 存下这个点的**所有大邻居**
当一个点的颜色从`white -> black`的时候，遍历**修改点的所有大邻居**（大邻居数量只有 $$O(\sqrt{m})$$ 级别）
**所有大邻居** $$y$$ 的 `ans[y] += 1`，如果从`black->white`，那么 `ans[y] -= 1`

这样统计的时候，大点的答案可以 $$O(1)$$ 得到

### 其他场景
对于 $$a_1 + a_2 +\cdots +a_n = n$$，那么 $$a_i$$ 只有 $$O(\sqrt{n})$$ 个不同的取值
对应的场景可能如下：

给你一个字符串 $$S$$，给你 $$q$$ 个询问，每个询问给定一个字符串 $$t_i$$
问 $$t_i$$ 在 $$S$$ 中出现多少次，满足 $$\sum |t_i| \leqslant 10^5$$

注意到 $$\sum |t_i| \leqslant 10^5$$，所以 $$t_i$$ 的长度 $$L$$ 只能有 $$\sqrt{n}$$ 种取值
由此我们可以考虑将所有长度都为 $$L$$ 的 $$t_i$$ 放到一起考虑

可以先 $$O(n \sqrt{n})$$ 预处理，扫描一遍 $$S$$，将长度为 $$L$$ 的串用一个哈希表存下来
`vector< map<string, int> > v`
这样 `v[L]` 就保存了所有长度为 `L` 的串的信息，当然为了保证时间复杂度
这里 `map<string, int>` 可以用 `map<ull, int>` 来替换，这里 `ull` 是**字符串哈希之后的值**
> `map<ull, int> cnt`，`cnt[ str ]` 表示 `str` 出现的次数

这样对于每个查询，可以直接查哈希表得出

上一篇：笛卡尔树和一些杂项数据结构下一篇：codeforces 721，数据结构优化问题

看完文章有啥想法