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)。对于不会莫队二次离线的同学请先学习之后再来尝试本题。 在学会莫队二次离线之后本题的难度就不高了。稍有卡常,不是特别严重。

题目列表

  • [Ynoi2018] 未来日记
  • [Ynoi2018] 天降之物
  • [Ynoi2018] 五彩斑斓的世界
  • [Ynoi2018] 末日时在做什么?有没有空?可以来拯救吗?
  • [Ynoi2018] 駄作
  • [Ynoi2019] 魔法少女网站
  • [Ynoi2019] 美好的每一天~ 不连续的存在
  • [Ynoi2019] Happy Sugar Life
  • [Ynoi2018] GOSICK