Ynoi 大分块系列

前言

关于做这个题单的目的，主要是许多人想切大分块，但却对 Ynoi 没有什么了解。

关于 Ynoi 的年份，大分块系列从 2018 开始编号，目前编至 2019；其余 Ynoi 系列数据结构题从 2017 起向前编号，其中不乏有许多好题值得大家一做。

对于大分块的编号，lxl 并没有给过解释。但是大分块的难度与编号顺序无关。lxl 对每个大分块都给出过难度评分供大家参考。

如果有新的大分块系列题目公布，我会及时在这里更新。

最初分块

P4119 [Ynoi2018]未来日记

题意简述：

给定一个长为 n 的序列 a，有 m 次操作。

把区间 [l,r] 内所有的 x 变成 y。
查询区间 [l,r] 内第 k 小值。

难度评分：8.5。

这道题最初出给了多校，后来被搬到了毛营，是 Ynoi 大分块系列第一个被出出来的题目。

有一点卡常，建议先思考如和用分块解决区间 kth 问题再考虑修改。个人认为难度评分虚高。

第二分块

P4117 [Ynoi2018]五彩斑斓的世界

题意简述：

给定一个长为 n 的序列 a，有 m 次操作。

把区间 [l,r] 中大于 x 的数减去 x。
查询区间 [l,r] 中 x 的出现次数。

难度评分：6。

这道题最初是 lxl 出给 CF 的，在 CF 里的编号是 CF896E，与那个~~臭名昭著的~~ ODT 的板子题属于同一场比赛。

在赛后，lxl 加强了这题的数据~~并卡了卡常~~，然后放进了洛谷题库。

算是大分块中的入门题，个人认为是该系列中最简单的题。

第四分块

P5397 [Ynoi2018]天降之物

题意简述：

给定一个长为 n 的序列 a，有 m 次操作。

把序列中所有值为 x 的数的值变成 y。
找出一个位置 i 满足 a_i=x，找出一个位置 j 满足 a_j=y，使得 |i-j| 最小，并输出 |i-j|。

难度评分：6。

这个分块有根号分治和序列分块两种做法，根号分治相对简单，但序列分块可以加强本题，将本题的全局修改变成区间修改。

对于原题而言难度其实不大，lxl 认为这是大分块系列中最简单的题。

序列分块版本有兴趣的同学可以去玩一玩（

第六分块

P4118 [Ynoi2018]末日时在做什么?有没有空?可以来拯救吗?

题意简述：

给定一个长为 n 的序列 a，有 m 次操作。

把区间 [l,r] 内所有数都加上 x。
查询区间 [l,r] 内的最大子段和，可以不选数。

难度评分：7.5。

这个题还有一个弱化版，是全局操作的版本。

需要一定的计算几何基础，同时卡常严重，代码难度高，建议谨慎食用。

第七分块

P5399 [Ynoi2018]駄作

题意简述：

给定一棵 n 个节点的树，结点标号从 1 到 n 。

定义树上两点 a,b 的距离 d(a,b) 是最小的非负整数 k ，满足存在结点序列 v_0,v_1,...,v_k ，满足 v_0=a,v_k=b ，且对于 0\leq i\leq k-1 有 v_i 和 v_{i+1} 之间在树上有一条边相连。

有 m 个询问，每个询问包含参数 p_0,d_0,p_1,d_1 ，求：

\sum\limits_{d(p_0,a)\leq d_0}\sum\limits_{d(p_1,b)\leq d_1}d(a,b)

难度评分：10。

这个题是大分块系列中最难的一题，从评分就能看出。

需要有树分块基础，以及高超的代码、卡常、调试能力。不建议写。

第十分块

P6578 [Ynoi2019]魔法少女网站

题意简述：

给定一个长为 n 的序列，定义区间 [l,r] 的子区间为所有形如 [l',r'] 的区间，满足 l',r' 为整数，且 l \le l' \le r' \le r。有 m 次操作：

1 x y：将 x 位置的值修改为 y。
2 l r x：查询区间 [l,r] 中有多少子区间的最大值小于或等于 x。

难度评分：6。

同样也算是 Ynoi 系列中比较简单的一道题，难度不高，卡常也不严重。个人认为是一道比较不错的分块练手题。

第十一分块

P6580 [Ynoi2019]美好的每一天~不连续的存在

题意简述：

给定一个数组 A,以及一棵 n 个节点的树，每个点有一个颜色，颜色为 1 到 x 的整数。

有 m 次查询，每次查询树上只保留 [l,r] 内的所有节点，设一个极大连通块中出现奇数次数的颜色个数为 t，则其对答案的贡献为 A_t ，即答案是所有连通块贡献的和，询问间互相独立。

难度评分：[6,10](未定）。

出自某场洛谷月赛，赛时似乎无人 AC。

这题的莫队涉及到一个比较神奇的 trick。做本题需要有一定的回滚莫队基础，有一点卡常。

评分未定的原因是 lxl 无法确定该 trick 的思考难度。

第十三分块

P6579 [Ynoi2019]Happy Sugar Life

题意简述：

给定一个二维平面，记平面上两个点 (x_1,y_1),(x_2,y_2) 构成支配对（记为(x_1,y_1)\le (x_2,y_2)）当且仅当 x_1\le x_2,\;y_1\le y_2。平面上初始给定 n 个不同的点 \{(x_i,y_i)\}_{i=1}^n。

你需要回答 m 次询问，每次询问给出两个点 (x,y),(x',y')，问有多少二元组 (i,j) 满足 (x,y)\le (x_i,y_i)\le (x_j,y_j)\le (x',y') 且 i \neq j。

难度评分：6.5。

这个题还有个脍炙人口的名字：时代的眼泪，也就是 \operatorname{NOI2020} 的 day1t3 ~~所以大家可以借此了解一下大分块有多恐怖~~。

在 NOI 时，本题的卡常不是很严重，复杂度正确的算法都能通过。但由于存在多种不同的做法，对应的常数及空间复杂度不相同，于是 lxl 卡掉了一些空间较劣的算法~~并卡了卡常~~，放入了洛谷主题库。

建议直接做时代的眼泪这题，对于本题不建议写。

第十四分块

P5398 [Ynoi2018]GOSICK

题意简述：

给定一个序列 a，每次询问给一个区间 [l,r]。

查询 l \leq i,j\leq r，且 a_i 是 a_j 倍数的二元组 (i,j) 的个数。

难度评分：8。

本题涉及莫队二次离线。莫队二次离线，是由 lxl 提出的一种算法，于某次洛谷月赛公开。当时的题目是第十四分块(前体)。对于不会莫队二次离线的同学请先学习之后再来尝试本题。

在学会莫队二次离线之后本题的难度就不高了。稍有卡常，不是特别严重。