当前位置：首页 > news >正文

[Record] Ynoi2018+ 大分块系列

news 2025/10/2 15:31:25

目录&概述

代码能力太差了，慢慢把这个系列写完吧……

Ynoi 大分块系列题单链接：https://www.luogu.com.cn/training/44148

最初分块：P4119 [Ynoi2018] 未来日记
第二分块：P4117 [Ynoi2018] 五彩斑斓的世界
第四分块：P5397 [Ynoi2018] 天降之物
第六分块：P4118 [Ynoi2018] 末日时在做什么？有没有空？可以来拯救吗？
第十分块：P6578 [Ynoi2019] 魔法少女网站
十一分块：P6580 [Ynoi2019] 美好的每一天~ 不连续的存在
十三分块：P6579 [Ynoi2019] Happy Sugar Life
十四分块：P5398 [Ynoi2018] GOSICK

最初分块：[Ynoi2018] 未来日记

难度评分：\(8.5\)。

Task

给定长度为 \(n\) 的序列 \(\{a_i\}_{i=1}^{n}\)，共有 \(m\) 次操作，操作属于以下两种：

给定 \(l,r,x,y\)，将区间 \([l,r]\) 中所有等于 \(x\) 的元素赋值为 \(y\)。
给定 \(l,r,k\)，查询区间 \([l,r]\) 中的第 \(k\) 小值。

所有输入均为小于等于 \(10^5\) 的正整数。

Solution

首先考虑静态版本的区间第 \(k\) 小分块做法，很容易做到 \(O(n\sqrt{n})\)。

对序列和值域同时进行分块。设 \(sum1_{i,j}\) 表示前 \(i\) 个序列分块中等于 \(j\) 的元素个数，\(sum2_{i,j}\) 表示前 \(i\) 个序列分块中值域分块属于第 \(j\) 个块的元素个数。查询时先确定第 \(k\) 小值属于哪一个值域分块，再在块内找到该元素，可以做到 \(O(\sqrt{n})\) 询问。

考虑如何处理第一种操作，可以发现，事实上将所有等于 \(x\) 的元素赋值为 \(y\) 可以使用并查集维护，且并查集只会合并两个连通块的根，此时并查集的均摊复杂度为 \(O(1)\) 而非 \(O(\alpha)\) 或 \(O(\log n)\)。因此只需要使用一个全局的并查集将相同值的位置合并起来，再对每个序列分块记录 \(rt_{i,j}\) 表示第 \(i\) 个块中某个值为 \(j\) 的元素的位置，即可实现修改和对散块的重构。

这道题卡常，可以在重构散块时只将值等于 \(x\) 的元素重构，合并到 \(y\) 子树中，对程序效率有明显提升。

时间复杂度 \(O(n\sqrt{n})\)。

Code

提交记录&代码链接：https://www.luogu.com.cn/record/227625689

第二分块：[Ynoi2018] 五彩斑斓的世界

难度评分：\(6\)。

Task

给定长度为 \(n\) 的序列 \(\{a_i\}_{i=1}^{n}\)，共有 \(m\) 次操作，每次给定 \(l,r,x\)，操作属于以下两种：

将区间 \([l,r]\) 中所有大于 \(x\) 的元素减去 \(x\)。
查询区间 \([l,r]\) 中等于 \(x\) 的元素个数。

数据范围 \(1\leq l\leq r \leq n\leq 10^6,1\leq m\leq 10^5,0\leq a_i,x\leq 10^5+1\)。

Solution

考虑全局如何查询，可以发现第一种操作有两种维护方式：

将所有大于 \(x\) 的元素减去 \(x\)
将所有小于等于 \(x\) 的元素加上 \(x\)，全局打 \(-x\) 的加标记。

综合两种做法，设 \(V\) 为当前所有元素中的最大值，当 \(x>\frac{V}{2}\) 时，采取第一种方式维护；当 \(x\leq\frac{V}{2}\) 时，采取第二种方式维护。此时可以发现，对于需要修改的元素，其原本值与修改后的值始终在值域上处于 \(\frac{V}{2}\) 这条分界线的两侧，可以使用并查集将 \((i,i+x)\) 或 \((i,i-x)\) 这样的二元组暴力合并表示修改到同一个值，与最初分块类似，并查集的均摊复杂度为 \(O(1)\)。由于每次需要使用并查集暴力修改的元素个数与每次修改后值域范围减少的量是相等的，因此值域大小为总势能，复杂度是 \(O(n)\) 的。

在区间修改查询问题上，可以分块，对于整块沿用以上做法，散块暴力修改查询。需要解决的问题是空间限制，但可以发现，将所有询问离线处理，每块的贡献是完全独立的，依次处理每个分块对询问的贡献，此时只需要使用一个块所需的空间即可。

这道题不卡常，不需要常数优化技巧。

时间复杂度 \(O(\sqrt{n}(m+V))\)。