Ynoi根号部分杂谈

· · 个人记录

静态区间逆序对，区间众数

P5046 [Ynoi2019 模拟赛] Yuno loves sqrt technology I

强制在线区间逆序对，做法是预处理，然后整块散块分开算贡献，复杂度刚好平衡，常数很大，比较卡常。

P5047 [Ynoi2019 模拟赛] Yuno loves sqrt technology II

区间逆序对离线做法，二次离线模板，常数很小也比序列分块好写。

P5048 [Ynoi2019 模拟赛] Yuno loves sqrt technology III

区间众数，特别小清新的分块，常数很小， n=5\times10^5 2s 稳过。

当然具体用到区间逆序对，众数的时候往往并不完全是板子，需要很多细节处理。

P7882 [Ynoi2006] rsrams

题意就是求一个区间的所有子区间的绝对众数之和，如果没有绝对众数那么那个区间绝对众数就是 0。

对于判断一个数 c 是否能成为一个区间的绝对众数，我们可以把所有为 c 的位置赋值成 1，其他赋值成 -1，一个区间绝对众数是 c 当且仅当区间和大于 0。

做个前缀和过后不难发现问题变成求区间顺序对数。

考虑对颜色出现次数根号分治。

$cnt > B$ ，直接二次离线莫队是会死的，因为这相当于把原问题加强了，不难发现 $|s_i - s_{i-1}| \leq 1$ ，于是用个桶普通莫队就行，但是序列长度还是 $n$ ，于是还得优化，把 $n'$ 降到 $cnt$ 级别。 1 的个数是与 $cnt$ 相同的，考虑对每个 1 找前边，后边的第一个 -1，然后构造一个等价的新序列，不难发现新序列长度 $n' \leq 3cnt$ ，做 $n'\sqrt m$ 的莫队就行了。 ## P7448 [Ynoi2007] rdiq 主要讲述了 nb 的二维数组 $O(\sqrt n)$ 单点加，$O(1)$ 二维求和。 这个题直接二离套用这个就行了，做法跟博丽灵梦差不多的。 --- 还有个经典的莫队题就是 P5355 [Ynoi2017] 由乃的玉米田 ## P5355 [Ynoi2017] 由乃的玉米田 前三个用 bitset 配合莫队是简单的，但除法会出点问题，当 $x \leq B$ 的时候复杂度 $O(\frac n x)$ 有些吃不消。 但这些 $x$ 只有 $B$ 个，考虑单独处理。 离线对每个 $x$ 做一遍扫描线，对每个 $r$ 求最早的一个 $l$ ，满足 $l, r$ 中存在 $a, b$ 有 $\frac b a = x$ ，扫的时候拿个桶对每个 $b$ 存最晚的一个 $ax = b$ ，记录答案只需要判断 $mi_r \ge l$ 就行 , $mi$ 是每个 $r$ 最晚的合法的 $l$ ，单次复杂度是 $O(n+V)$ 的，做 $B$ 次完全不会超时限。 --- 扣掉莫队的简单题和莫队与根号分治配合的题，还有一大类题就是序列分块。 先从小的讲起。 ## P5356 [Ynoi2017] 由乃打扑克 区间加区间第 $k$ 大，直接做可以做到 $n\sqrt n \log n$ ，分散层叠最低能优化到 $n \sqrt {n \log n}$ （默认 $n,q$ 同阶）。 具体讲下直接分块的实现，首先查询是要二分，然后变成查区间小于等于 $x$ 的数的个数。 散块查是 $O(B)$ 的，整块是 $O(\frac n B \log B)$ 的，乘上二分过后发现复杂度上天了。 其实散块可以提前归并到一起，而且每次查询归并只用做一次，这是 $O(B)$ 的，然后每次二分的查询变成 $\log B + \frac n B \log B$ ，然后 $B$ 取 $\sqrt n \log n$ 时平衡，总复杂度变成 $n \sqrt n\log n

P3712 少女与战车

这个题直接先 dfs 序把树拍扁，只要你的实现没锅，套用上边的分块就能过，但因为至于很小所以还有别的阴间做法。

谈几个大分块的经典题。

P4117 [Ynoi2018] 五彩斑斓的世界

大分块入门题，考虑 >x 减去 x 的性质。

记一个块最大值为 mx

对于一个块，假如 mx > 2x 那么直接暴力，打个整体减 x 的 tag，然后把实际值 <x 的加上 x，复杂度是 O(x) 的，mx 变化量也是 x

假如 mx \leq 2x ，我们先给整个块打个整体加 x 的 tag ，然后把实际值 >x 的减去 x，复杂度是 O(mx-x) 的，mx 变化量也是 mx - x

而一个块的 mx 总变化量是 V 于是复杂度 O(\frac {Vn} B) ，空间也是相同的，所以考虑离线滚块将空间降到线性。

P4119 [Ynoi2018] 未来日记

区间将 x 替换成 y ，区间查第 k 小。

区间第 k 小的查询可以用序列分块配合值域分块完成。

替换还是考虑用并查集状的东西维护，不难发现一个块颜色数（数的种类数）是不断减少的，考虑替换的时候假如这个块含 x 并且含 y 直接暴力重构，这个最多做 O(B) 次，每次 O(B) ，然后假如含 x 并且不含 y ，把 x 用并查集替换到 y 上去。

主要难度在实现。

P7710 [Ynoi2077] stdmxeypz

小弱智题，先 dfs 序拍扁树，然后根号分治模数 a ，用不同的分块维护就行了，空间随便卡卡就过了，乱取块长都能过。

所以为啥能有黑？

P7446 [Ynoi2007] rfplca

弹飞绵羊的强化版。

考虑同样的方式维护，对每个块维护两个数组 f,g ，分别是跳出当前块以及在块内跳。

考虑每次修改暴力重构一下，经过 B 次重构过后不难发现当前块里边的数一次就能跳出当前块，于是直接维护块内加的 tag 就行了。

求 lca 的过程类似树剖，慢慢跳，不难发现出块次数是 O(B) 的，所以复杂度是对的。

P4690 [Ynoi2016] 镜中的昆虫

区间覆盖区间数颜色。

Trick 题，考虑对每个数维护数组 f_i 为下一个与它相等的数的位置。

不难发现 f 的修改也是 O(n+q) 的级别的。

不难发现查询变成 \sum_{i=l}^r\limits [f_i>r] 是个二维偏序的形式，于是用个序列分块套 O(B) 修，O(1) 查的值域分块。用 cdq 也可以。

为了卡空考虑离线滚块，常数很小轻松过。

P5397 [Ynoi2018] 天降之物

卡常题，全局做法是根号分治，分类讨论出现次数 >B 的以及 \leq B 的数，然后查询。

但是此题有序列分块做法，具体是维护块内答案，以及数的出现位置，然后从左往右扫。

块内只有 B 个数，所以块内答案重新编号后是 O(B^2) 的。

而一次单点修也只会改变一种数与其他数的答案，不难发现只会修改 B 个值。

然后就完了。势能一下发现可以支持把区间的 x 修改成 y ，这就是手牵手走向明天那个题，然而和牛客模拟赛撞题了（我们考CSP模拟赛竟然考了这场）

简单的东西差不多就这些了。