静态区间逆序对，区间众数
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 \leq B\) ，\(c\) 成为绝对众数的区间是 \(cnt^2\) 级别的，把这些区间取出来做分块的二维数点即可。
\(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模拟赛竟然考了这场）
简单的东西差不多就这些了。
标签：log,分块,复杂度,杂谈,Ynoi,sqrt,众数,区间 From： https://www.cnblogs.com/yzq-yzq/p/18575111