先嘴上，会在神秘时刻写代码。
最初分块 P4119 [Ynoi2018]未来日记
将区间内某个数变成另一个数，区间第 小。
区间第 小除了每块内部排序外，还可以值域分块。
具体地设 表示值域在 这一块，下标前 块内的个数，，表示 这个数在前 个块的个数，那么查询就先枚举所在块，然后在块内枚举答案，散块是容易处理的。
然后考虑修改，散块直接处理，整块内有三种情况：
- 源数不出现，忽略
- 源数出现，目标数不出现，在源数上打个标记。
- 源数出现，目标数出现，暴力重构。
能暴力重构的原因是第三种情况会使块内颜色数变小，而一开始这个势能总和是 ，一次修改只有修改到散块的时候才会增大势能，总势能不超过 。
因为修改只涉及到两种数，因此对值域分块的数组是好维护的。
时空复杂度都是根号。
第二分块 P4117 [Ynoi2018]五彩斑斓的世界
区间大于 的减去 ，查询区间某个数出现次数。
值域很小，考虑每个块维护一些关于块内最大值的势能变化。
记每个块的最大值为 ，现在有一个 操作。
- 直接枚举 内的所有数往下合并，然后 变成 。
- 直接枚举 内的所有数向上合并，然后打个整体减法标记。
这样就可以在 的时间复杂度内让 减去 ，然后每块内的势能就对了。
用并查集维护就可以支持查询，离线逐块处理做到线性空间。
第四分块 P5397 [Ynoi2018]天降之物
全局将某个数变成另一个数，查询全局数值 的点和数值为 的点各选出一个的最小距离。
没有修改就是根号分治，按出现次数分为大小数，查询两个小数暴力，有一个大数就预处理。
考虑带上修改怎么做，比较爆蛋的地方在于我让一个大数加入一个小数后要重构信息就炸了。
考虑定期重构，即对于每个大数，额外维护一个小集合，小集合内的元素个数不超过根号，当小集合大小超过范围后就重构这个大数，这样重构次数就对了。
时空复杂度都是根号。
如果加强到区间修改区间查询怎么做？
考虑序列分块，区间查询可以记录整块内部某个数第一次出现的位置和最后一次出现的位置，以及整块内部某两种颜色的最近距离，这样查询就可以直接拆成整块内部和整块对散块和散块对散块，都是好维护的。
考虑修改，利用最初分块的方法进行修改，修改的时候需要重新算出某两种颜色的最近距离，由于一次修改只涉及 种颜色，所以这是可以维护的。
第六分块 P4118 [Ynoi2018]末日时在做什么?有没有空?可以来拯救吗?
区间加正负数区间最大子段和。
区间最大子段和要维护的信息（最大子段和，最大前缀和，最大后缀和）是经典的凸包信息，最大子段和这个可以闵可夫斯基和维护。
对于块内建立线段树维护上述信息，这样可以支持整块打标记和整块查询。
考虑散块修改，重构线段树复杂度比较爆，但是可以在访问到的节点上打标记，然后重构剩下的有用节点，这样可以线性重构。
散块查询直接暴力。
先在瓶颈在于整块查询要在凸包上二分，带个 。
先离线下来逐块处理，注意到两次散块重构之间的操作均为全局加和全局查询，可以按全局查询时块内的 tag 排序变成增量问题，排序可以基数排序，然后这个就可以用一个双指针在凸包上扫了。
时间根号，空间线性。
也可以时间分块，这样问题就只剩下全局修改全局查询了，直接爬凸包。
第七分块 P5399 [Ynoi2018]駄作
不会做
第十分块 P6578 [Ynoi2019]魔法少女网站
单点修改，查询区间内最大值不超过 的子区间数量。
如果是静态问题可以直接离线扫描线，线段树维护 连续段解决。
现在带修了，时间分块即可，使用分块来平衡复杂度，不难发现是可以做的。
第十一分块 P6580 [Ynoi2019]美好的每一天~不连续的存在
给一棵树，每次只保留 内的点，然后形成的若干极大连通块中，若出现奇数次的点为 ，则这个连通块会产生 的贡献，求最后总贡献。
回滚莫队，移动右指针可以均摊，直接线段树合并维护这些信息。
但是移动左指针怎么办？
考虑按移动左指针的代价均摊移动复杂度，注意到 一定没有 的代价大，因此按下面的代价分块即可，总代价是 的。
这样就做到根号 ，由于线段树的 有点大，听说要写一些神秘的东西代替这个东西才能过。
第十三分块 P6579 [Ynoi2019]Happy Sugar Life/NOI2020 D1T3
不太会，听说是用 ylst1 的分块容斥硬搞。
第十四分块 P5398 [Ynoi2018]GOSICK
查询区间内一个数是另一个数的倍数的点对数。
二次离线，现在变成某个数在某个前缀内有多少个数是他的倍数/约数。
扫描线加入数字时，如果这个数字作为倍数出现，只需要更新这个数字的约数的答案即可，复杂度没问题。
如果这个数字作为约数出现，因为没有保证数字互不相同，没有调和级数的性质，比较爆。
对这个数字是否大于根号考虑，大于根号直接更新。
对于不大于根号的数字，考虑二次离线过程中产生的所有询问，要么是考虑某个点在上一个前缀中有多少是他的约数，这个可以直接算。要么是对于某个区间，他在一个固定的前缀内有多少是他的约数，因为已经钦定了作为约数的数字不超过根号，枚举这个数，然后就变成了前缀内这个数的出现次数乘上区间内是这个数的倍数的个数，可以前缀和 回答。
最后总复杂度根号。
本文作者：World Creater
本文链接：http://worldcreaterwc.github.io/ynoi/
版权声明：本博客中所有原创文章除特别声明外，均允许规范转载，转载请注明出处。所有非原创文章，按照原作者要求转载。