Ynoi 大分块系列
题单介绍
## 前言
关于做这个题单的目的，主要是许多人想切大分块，但却对 Ynoi 没有什么了解。
关于 Ynoi 的年份，大分块系列从 2018 开始编号，目前编至 2019；其余 Ynoi 系列数据结构题从 2017 起向前编号，其中不乏有许多好题值得大家一做。
对于大分块的编号，lxl 并没有给过解释。但是大分块的难度与编号顺序无关。lxl 对每个大分块都给出过难度评分供大家参考。
如果有新的大分块系列题目公布，我会及时在这里更新。
## 最初分块
[P4119 [Ynoi2018]未来日记](https://www.luogu.com.cn/problem/P4119)
题意简述：
给定一个长为 $n$ 的序列 $a$，有 $m$ 次操作。
- 把区间 $[l,r]$ 内所有的 $x$ 变成 $y$。
- 查询区间 $[l,r]$ 内第 $k$ 小值。
难度评分：$8.5$。
这道题最初出给了多校，后来被搬到了毛营，是 Ynoi 大分块系列第一个被出出来的题目。
有一点卡常，建议先思考如和用分块解决区间 kth 问题再考虑修改。个人认为难度评分虚高。
## 第二分块
[P4117 [Ynoi2018]五彩斑斓的世界](https://www.luogu.com.cn/problem/P4117)
题意简述：
给定一个长为 $n$ 的序列 $a$，有 $m$ 次操作。
- 把区间 $[l,r]$ 中大于 $x$ 的数减去 $x$。
- 查询区间 $[l,r]$ 中 $x$ 的出现次数。
难度评分：$6$。
这道题最初是 lxl 出给 CF 的，在 CF 里的编号是 [CF896E](https://www.luogu.com.cn/problem/CF896E)，与那个~~臭名昭著的~~ ODT 的板子题属于同一场比赛。
在赛后，lxl 加强了这题的数据~~并卡了卡常~~，然后放进了洛谷题库。
算是大分块中的入门题，个人认为是该系列中最简单的题。
## 第四分块
[P5397 [Ynoi2018]天降之物](https://www.luogu.com.cn/problem/P5397)
题意简述：
给定一个长为 $n$ 的序列 $a$，有 $m$ 次操作。
- 把序列中所有值为 $x$ 的数的值变成 $y$。
- 找出一个位置 $i$ 满足 $a_i=x$，找出一个位置 $j$ 满足 $a_j=y$，使得 $|i-j|$ 最小，并输出 $|i-j|$。
难度评分：$6$。
这个分块有根号分治和序列分块两种做法，根号分治相对简单，但序列分块可以加强本题，将本题的全局修改变成区间修改。
对于原题而言难度其实不大，lxl 认为这是大分块系列中最简单的题。
[序列分块版本](https://www.luogu.com.cn/problem/P5692)有兴趣的同学可以去玩一玩（
## 第六分块
[P4118 [Ynoi2018]末日时在做什么?有没有空?可以来拯救吗?](https://www.luogu.com.cn/problem/P4118)
题意简述：
给定一个长为 $n$ 的序列 $a$，有 $m$ 次操作。
- 把区间 $[l,r]$ 内所有数都加上 $x$。
- 查询区间 $[l,r]$ 内的最大子段和，可以不选数。
难度评分：$7.5$。
这个题还有一个[弱化版](https://www.luogu.com.cn/problem/P5073)，是全局操作的版本。
需要一定的计算几何基础，同时卡常严重，代码难度高，建议谨慎食用。
## 第七分块
[P5399 [Ynoi2018]駄作](https://www.luogu.com.cn/problem/P5399)
题意简述：
给定一棵 $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]魔法少女网站](https://www.luogu.com.cn/problem/P6578)
题意简述：
给定一个长为 $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]美好的每一天~不连续的存在](https://www.luogu.com.cn/problem/P6580)
题意简述：
给定一个数组 $A$,以及一棵 $n$ 个节点的树，每个点有一个颜色，颜色为 $1$ 到 $x$ 的整数。
有 $m$ 次查询，每次查询树上只保留 $[l,r]$ 内的所有节点，设一个极大连通块中出现奇数次数的颜色个数为 $t$，则其对答案的贡献为 $A_t$ ，即答案是所有连通块贡献的和，询问间互相独立。
难度评分：$[6,10]$(未定）。
出自某场洛谷月赛，赛时似乎无人 AC。
这题的莫队涉及到一个比较神奇的 trick。做本题需要有一定的回滚莫队基础，有一点卡常。
评分未定的原因是 lxl 无法确定该 trick 的思考难度。
## 第十三分块
[P6579 [Ynoi2019]Happy Sugar Life](https://www.luogu.com.cn/problem/P6579)
题意简述：
给定一个二维平面，记平面上两个点 $(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$。
这个题还有个脍炙人口的名字：[时代的眼泪](https://www.luogu.com.cn/problem/P6774)，也就是 $\operatorname{NOI2020}$ 的 $day1t3$ ~~所以大家可以借此了解一下大分块有多恐怖~~。
在 NOI 时，本题的卡常不是很严重，复杂度正确的算法都能通过。但由于存在多种不同的做法，对应的常数及空间复杂度不相同，于是 lxl 卡掉了一些空间较劣的算法~~并卡了卡常~~，放入了洛谷主题库。
建议直接做时代的眼泪这题，对于本题不建议写。
## 第十四分块
[P5398 [Ynoi2018]GOSICK](https://www.luogu.com.cn/problem/P5398)
题意简述：
给定一个序列 $a$，每次询问给一个区间 $[l,r]$。
查询 $l \leq i,j\leq r$，且 $a_i$ 是 $a_j$ 倍数的二元组 $(i,j)$ 的个数。
难度评分：$8$。
本题涉及莫队二次离线。莫队二次离线，是由 lxl 提出的一种算法，于某次洛谷月赛公开。当时的题目是[第十四分块(前体)](https://www.luogu.com.cn/problem/P4887)。对于不会莫队二次离线的同学请先学习之后再来尝试本题。
在学会莫队二次离线之后本题的难度就不高了。稍有卡常，不是特别严重。