lxl是yyds
大力分块
我估计会长的一比
背景
众所周知，lxl喜欢数据结构
众所周知，lxl很毒瘤
众所周知，lxl有点中二+宅
于是lxl出了Yn（由乃）oi的大分块题目，把以上三者结合了起来
然后，就让我们来大力分块吧！
最初分块
「望月悲叹的最初分块」
维护一个序列，支持区间修改（把所有的 $x$ 变成 $y$ ）和区间第 $k$ 小， $n, m, a \le 10^5$
做题
当然考虑分块
先设块长为 $B = \sqrt{n}$ ，考虑询问，先找到询问的区间，这个区间必定是由整块+散点组成，而这步寻找可以 $O(1)$ 找到
注意到 $a \le 10^5$ ，值域与 $n$ 同级，考虑对值域也分块（为区分称其为值块），设块长为 $V = \sqrt{n}$ ，记 cnt[i][j] 表示第 $i$ 块内的数值在第 $j$ 值块内的有几个
但是这个区间最多有 $\sqrt{n}$ 个块，又最多要枚举 $\sqrt{n}$ 个值块，这显然不可接受，由于对于单次询问，包括的块不变，考虑对块进行前缀和，设 cnt[i][j] 表示前 $i$ 块内的数值在第 $j$ 值块内的有几个，再开一个临时数组 tcnt[j] 表示散点中数值在第 $j$ 值块内的有几个，枚举可得答案所在值块，我们发现同理可得答案，具体的，设 rel[i][j] 表示前 $i$ 块内的数值是 $j$ 的有几个， trel[j] 同理，枚举可得答案，注意到枚举 cnt[i][j] 的时间是 $O(\sqrt{n})$ 的（只用枚举 $j$ ），枚举 rel[i][j] 也是 $O(\sqrt{n})$ 的，于是，我们用单次 $O(\sqrt{n})$ 的时间（目前看来）， $O(n \sqrt{n})$ 的空间（ rel 数组）解决了询问
考虑修改，先看散点，明显暴力就行了，修改的区间也可以 $O(1)$ 找到，对于整块每次修改需要一并修改 cnt 和 rel ，并且由于他们是“前缀和”，必须要把后面的每个块都改了，时间是 $O(\sqrt{n})$ （注意这里不要每个块都去修改后面，那样是 $O(n)$ 的，应该记一个修改量的前缀和），就……行了？
行个鬼啊！区间在修改完后一定要打上懒标记，不然下一次单点修改时查到的就是错误的值啊！
发现区间修改有一个优美的性质：值相等的点无论如何一定相等，这启发我们打并查集（对每一块开一个），把相等的点直接并到一起，这样，区间的标记可以 $O(\log \sqrt{n})$ 解决，但是，副作用是：单点修改的时候怎么办？不能直接更改这个点的 $fa$ ，因为它下面可能还有点，直接重构其实是可以的办法（因为每次散点只在两个块，最多 $2\sqrt{n}$ 个点），但我们还有别的办法
考虑建一些辅助点，设点 nd[i][j] 代表第 $i$ 块值为 $j$ ，对于一个块里的点，把他们全都并到 $nd$ 上去（换句话说，只有 $nd$ 有儿子），这样，散点就直接改就行了，而整块可以让 nd[i][x] 的 $fa$ 改为 nd[i][y] ，并让 nd[i][x] = 0 （这代表这个区间没有值为 $x$ 的点），特殊情况是 nd[i][y] == 0 ，这个时候就新建一个节点（浪费空间ing）
考虑空间， $nd$ 数组大小为 $O(n \sqrt{n})$ ，因为最初有 $n$ 个点（它们不做父亲），每一块最多有 $\sqrt{n}$ 个值，每次操作最多加 $\sqrt{n}$ 个辅助点（每块一个），并查集的节点数最多是 $n + \sqrt{n} * \sqrt{n} + m * \sqrt{n}$ 可以看作 $O(n \sqrt{n})$ 的空间；而对于时间，并查集的修改都是 $O(1)$ 的，单点的查询是 $O(\log \sqrt{n})$ （这个 $\log \sqrt{n}$ 非常解决于 $1$ ，因为并查集的深度只有辅助点个数，加上有路径压缩），散点是 $O(\sqrt{n})$ 个，块是 $O(\sqrt{n})$ 个，而修改那两个数组要用 $O(\sqrt{n})$ ，单次修改的总时间为 $O(\sqrt{n} \log \sqrt{n})$ ，而由于单点的查询是 $O(\log \sqrt{n})$ ，上面的单次询问也变成了 $O(\sqrt{n} \log \sqrt{n})$
额……先打出来
（受苦了一下午以后……）
好，TLE $0pts$ ，wtm**lxl！！！，我只能望月悲叹
吃了个饭，回来尝试卡块长，发现 $B = 500, V = 317$ 是既不会TLE，也不会MLE，只是WA了，貌似有戏……？
开始调试受苦（这记着是为了防止我忘了，可以跳过不看） ：
$2022/1/24$ $18:00 \sim 20:50$ 自以为操作 $2$ 基本调试完毕
$2022/1/24$ $20:55$ 自以为调完然后交（
谁给我的自信），WA $10pts$ ，WA的点都是输出了负数，不知为何（疑似炸int？）$2022/1/24$ $21:00$ 发现负数是我调试的时候把范围改了没改回去，修正后手造大样例，结果WA了（幸好没交）
$2022/1/24$ $21:20$ 发现我的make date不够严谨，而且在大数据下操作 $2$ 也挂了
$2022/1/24$ $21:30$ 发现操作 $2$ 挂在没特判同块
$2022/1/24$ $21:51$ 同机房wfy巨佬帮我调出了一个很难的RE，这次应该是真的吧操作 $2$ 调好了
$2022/1/24$ $22:00$ $73pts$ 该睡觉了
话说我昨晚睡觉时想到，并查集上加一个按秩合并，可以优化到单次 $O(\sqrt{n} \alpha(n))$
$2022/1/25$ $8:00$ AC了！！！
做法如果还有不懂的可以看这个
代码
1 |
|
其它
我也喜欢我妻由乃！
第二分块
「突刺贯穿的第二分块」
好，我们乘胜追击！
维护一个序列，支持区间修改（把所有大于 $x$ 的数减去 $x$ ）和查询区间中 $x$ 的出现次数， $n \le 10^5, m \le 5 \times 10^5, a \le 10^5 + 1$ ，时限 $7.5s$ ，空间 $64MB$
做题
不难发现，如果不是那sm的空间，可以用最初分块解决，但这空间， $O(n \sqrt{n})$ 都开不出来
那看看着题和最初分块的不同呢？发现询问是出现次数，而不是排名，这个显然可以直接记录，就不必要前缀和了，注意，这意味着分块后每个块之间的信息毫无关联，并且答案就是区间包含的所有答案的累加于是有一个控制空间的方法：
把操作离线下来，对每个块都按顺序处理一遍所有的操作，然后把询问的答案累加即可，空间是 $O(n + m)$ 的了（也许开 short 也行，没试过）
那么该如何修改呢？注意到由于我们离线了，所以要枚举 $\sqrt{n}$ 块，每一块又要枚举 $m$ 个操作，所以对于每个操作我们要做到 $O(1)$ ，或者所有操作加起来共用 $O(n)$
这……直接瞟一眼出题人的题解，发现可以这样懒标记+并查集维护，具体的，设当前块最大值为 $mx$ ：
- 若 $mx \le 2x$ ，就直接枚举大于 $x$ 的数，让它们减去 $x$
- 若 $mx > 2x$ ，就直接枚举小于 $x$ 的数，让它们加上 $x$ ，然后区间打上减 $x$ 的标记
设后面的“枚举……”时间复杂度为 $O(t)$ ，发现 $mx$ 的真实值（算上懒标记）是单调下降的，由于 $mx$ 初始最大为 $10^5 + 1$ ，所以所有操作时间加起来是 $O(a) * O(t)$ 的，由于总共只能用 $O(n)$ ，所以必须保证 $O(t) = O(1)$
还是可以开并查集（但这里可不能像最初分块一样开辅助点，空间不够），对每个值开一个并查集，然后记录这个并查集的 $si$ ，整块修改的时候直接合并两个值的并查集，查询的时候直接输出这个并查集的 $si$ ，都是 $O(1)$ 的；如果是散点修改，就直接重构；散点查询，就通过并查集找到范围内每个数的值，暴力统计即可
但对于散点的时间，我们还得从另一个角度分析才能得出结论：假设我们没有离线，空间就开那么大，则 $m$ 次操作最多重构 $2m$ 个块，每个块 $\sqrt{n}$ 个点，同时怼上路径压缩，由于每次会遍历每个叶子，路径压缩的效果极好，散点均摊每个点可以当作 $O(1)$ ，则时间复杂度为 $O(m \sqrt{n})$ ，均摊到每个块和每个操作，就是 $O(1)$ 了（好像严格的 $O(1)$ 应该是用链表代替并查集，重构更快，但不太好打）
代码
1 |
|
其它
这是个galgame吗？我好像没玩过……
第三分块
由于lxl觉得它过于简单，被开除块籍了，后面数字断了的就是开除块籍了，不再提
第四分块
「弑尽破净的第四分块」
维护一个序列，支持两种操作：
- 区间修改，把序列中所有的 $x$ 变成 $y$
- 在整个序列中找出一组 $i, j$ 满足 $a_i = x, a_j = y$ ，使 $|i - j|$ 最小，并输出 $i - j$ ，不存在输出Ikaros
强制在线， $n, m, a \le 10^5$ ， $500ms, 256MB$
做题
额……操作全都是对序列中进行，分个鬼的块啊！但是毕竟这是“第四分块”，加上出题人lxl，估计还得分，就硬分！
还是考虑对序列分块，同时记录每一块内每一个数的个数，对于询问，如果有一个块同时包含两个数，直接暴力，时间 $O(B)$ ；否则吧每个块当成一个点，点上只有 $x, y, 0$ 三种信息，找到最近的 $x, y$ ，整块直接加，散点暴力，时间为 $O(2B + \frac{n}{B})$ ，修改就并查集维护即可，考虑到每次修改是对于整个序列，可以所有数共用一个并查集，不存在散点的情况，块长取 $B = \sqrt{n}$ 时，时空复杂度为均为 $O(n \sqrt{n})$ ，希望它别卡常……
艹，打到一半意识到这是完全假的，因为可能会有多个块同时包含两个数，而且还有可能出现两个相邻块最优，或者多个跨块最优……总之就是完全假掉了
臭不要脸的康康题解~
原来正解是根号分治（那为啥要叫第四分块啊！不过好像有人分块卡过了），不过既然是学习，当然学更稳当的根号分治了（就是平衡时间复杂度）
在讲正解前，先明确一些东西：
先考虑暴力的做法，当然是对每个数维护一个有序的位置集合，合并时归并排序，查询类似归并用双指针，但不合并，据说这样有 $60pts$ （夭寿了！lxl出的题有暴力分了！）
设 si[x] 表示 $x$ 在序列中出现的次数，当 si[x] > lim （ $lim$ 是阈值）时称其为大点，否则是小点；定义数组 as[x][y] 有意义当且仅当 $x$ 是大点，其意义为“大点 $x$ 到值 $y$ 的最小距离”；定义附属集合 v[x] 表示“自上一次重构以来，新出现的 $x$ 的位置”
我们要保证所有附属集合的大小不超过 $lim$ ，具体的，每当一个点 $x$ 的附属集合的大小超过 $lim$ ，我们就暴力跟新 as[x][] （此时 $x$ 必为大点），暴力可以做到 $O(n)$ ，我们称这个操作为重构
另外，在修改操作把 $x$ 变成 $y$ 时，可以开一个数组 val[x] 代表值 $x$ 的真实值，这样我们就可以交换 $x, y$ 了，只要记得只要修改一下 $val$ 即可
好，现在来看根号分治：
因为 $x, y$ 可以交换，所以只考虑 si[x] <= si[y] 的情况
对于修改，设把 $x$ 变成 $y$
- 若 $x$ 是小点，暴力归并二者的附属集合（把 $x$ 并入 $y$ ）；如果合并后（这是预判，不必真的合并） $y$ 的附属集合大小超过 $lim$ 就重构 $y$
- 若 $x$ 为大点（此时 $y$ 必为大点），显然把 $x$ 当成 $y$ 直接暴力重构（为啥不合并呢？因为 $x$ 是大点，它的一部分答案信息已经在
as[x][]里了，附属集合记录信息不完全）
重构发生会把至少 $lim$ 个数从附属集合里除去，它们的信息被记在了 $as$ 中，且它们不会在出现在任何附属集合内了，而当所有附属集合都为空时，显然不会再发生重构，所以重构最多发生 $\frac{n}{lim}$ 次
合并附属集合显然是 $O(lim)$ ，不重构只修改 as[][y] 是 $O(\frac{n}{lim})$ 所以修改的时间复杂度为 $O(m * \max(lim, \frac{n}{lim}) + n * \frac{n}{lim})$
对于查询 $x, y$
先暴力“归并”（不合并）二者附属集合，再与两个数中大点的 $as$ 取 $\min$
查询的时间为 $O(m * lim)$
最后关于空间，最多有 $\frac{n}{lim}$ 个大点，而每个点的附属集合最多有 $lim$ 个数，所以空间为 $O(\frac{n}{lim} * a + n * lim)$ ，另外一定注意 vector 的 clear 不释放空间，具体写法见代码
明显，因为 $n, m, a$ 同级， $lim = \sqrt{n}$ 时时空都达到最优（然而实际上一般出题人都会卡 $\sqrt{n}$ 的，开大点可能好些，但本题不必）
代码
1 |
|
其它
天降之物也挺好看的，但可惜 $09$ 年是钢炼的天下
未完待续
在写到这里时，已经 $7000$ 字了，才完成 $\frac{1}{3}$ ，觉定分成几部分（目前想的是三篇，到时候看吧）
已经打了两天的分块了，我都要吐了，缓缓再战，下一篇写好会在这里挂链接的
update：大力分块2