根号算法学习笔记

SDSC Day2，ckw讲的根号算法……静态分块、动态分块、莫队、树上莫队、回滚莫队等等。“入坟难度”，ckw如是说。

一、分块

分块的本质是分治。与线段树不同的是，它不是合并两个儿子，而是合并连续的几块。分块常用于不能“快速合并”的情况。

1. 静态分块

内涵就是预处理到块。

经典的区间众数（强制在线）思路：

1. 预处理 \(ans[l,r]\) 数组，记录 \([l,r]\) 块的信息（区间众数）；
2. 对于询问，如果在一块内，直接暴力，不超过 \(O(\sqrt n)\) ；
3. 不在一块内，要么是 \(ans[bl,br]\) ，要么在“零散块”里出现，所以要统计零散块里出现的数字在整个询问区间 \([l,r]\) 中的出现次数；
4. 枚举“零散块”里的数字已经是 \(O(\sqrt n)\) 级别了——开一个“前缀桶”, \(O(1)\) 求出连续块中的情况，再对“零散块”开桶跑 \(\sqrt n\) 暴力。

问题是 \(ans\) 数组怎么求：没有听懂 * 1。

2. 动态分块

有 6 个子问题：

1. 单点修改 \(O(1)\) ，区间查询 \(O(\sqrt n)\) ;
2. 单点修改 \(O(\sqrt n)\) ，区间查询 \(O(1)\) ;
3. 区间修改 \(O(1)\) ，单点查询 \(O(\sqrt n)\) ;
4. 区间修改 \(O(\sqrt n)\) ，单点查询 \(O(1)\) ;
5. 插入 \(O(1)\) ，求第 \(k\) 小 \(O(\sqrt n)\) ;
6. 插入 \(O(\sqrt n)\) ，求第 \(k\) 小 \(O(1)\) ;

有对应的解决思路：

1. 直接修改；
2. 修改自己块的和后面块的，差分；
3. 差分转化为情况2；
4. 逐块打标记；
5. 值域分块；
6. 值域分块，维护第 \(k\) 小在第几块和每一块内的数。

二、莫队

1. 莫队

P1972 HH 的项链（72分）。离线下，从一个询问区间转移到下一个——排序询问，存在一种询问序列，使得这个暴力达到 \(O(n \sqrt n)\) 级别。

排序方式：分块，以左端点所在块为第一关键字，右端点为第二关键字。

为什么是对的？分类讨论。

1. \(l_i\) 和 \(l_{i+1}\) 在同一块内：时间复杂度为 \(O(|l_i-l_{i+1}|+|r_i|)\) ,前者 \(O(\sqrt n)\) 级别，后者加起来 \(O(n)\) 。
2. \(l_i\) 和 \(l_{i+1}\) 不在同一块内：加起来 \(O(n)\) 。

1/2 常数优化：奇偶性分，右端点从小到大还是从大到小。

用值域分块平衡复杂度：没有听懂 * 2 。

2. 树上莫队

将树化为链，转为普通莫队。

写出“入栈出栈序”，如果 \(x\) 是 \(y\) 的 LCA ，则取出 \(fir_x\) 到 \(fir_y\) ，否则取出 \(fir_x\) 到 \(sec_y\) 。取出的序列中出现奇数次的点在 \(x\) 到 \(y\) 的路径上，否则不在。注意，会漏掉 LCA ，要补上。

3. 回滚莫队