「杂题乱写」Ynoi

由于 Ynoi 道道卡常且常数受一些常量影响较大，为方便表示复杂度，本文记阈值为 \(B\)，块长为 \(L\)，块数为 \(C\) . 三者都比较接近 \(\sqrt{n}\) 但是需要根据具体常数调整 .

P7710 [Ynoi2077] stdmxeypz

考虑将问题转化到 dfn 序列上，子树修改转化为区间修改，考虑分块维护 . 散块是容易直接处理的，如何处理整块？

感觉很可以根号分值！设阈值为 \(B\)，对于 \(x>B\)，修改的点的数量不超过 \(\frac{n}{B}\) 但是并不方便直接暴力修改，考虑开一个标记数组 \(g_{i, j}\) 表示 \(i\) 的子树内与 \(i\) 距离为 \(j\) 的点的标记；对于 \(x\le B\)，可以直接打上一个标记 \(f_{i, j}\) 表示该块内所有 \(dep_u\equiv j\bmod(i)\) 的点 \(u\) 的标记 . 查询时把所在块的标记跑一边加上 .

注意到根号分值的阈值不必和块长一样，否则不会 TLE 会 MLE .

预处理 \(O\left(n\right)\)，修改 \(O\left(L + \min\left(C, \dfrac{n}{B}\right)\right)\)，查询 \(O\left(B + C\right)\) .

Luogu Submission .

P5356 [Ynoi2017] 由乃打扑克

你发现 k-th 很难，但是 rank 好像更可做一点，于是二分，维护区间 rank .

不难想到对每个块排序，区间修改整块打标记，散块直接重构；区间 rank 整块 upper_bound，散块暴力跑一遍 .

但是感觉这个散块直接重构直接重构太耗时了，怎么办呢？发现一个块内没更改的部分是有序的，更改的部分也是有序的，那么考虑归并排序就把复杂度由 \(O(L\log L)\) 降到了 \(O(L)\) .

预处理 \(O\left(n\log L\right)\)，修改 \(O\left(L + C\right)\)，查询 \(O\left(\log V\left(L + C\log L\right)\right)\)（内层 \(\log\) 来源于常数较小的 upper_bound） .

Luogu Submission .

P5309 [Ynoi2011] 初始化

和 stdmxeypz 有点像吧！为啥我不是先做的这个题？

依旧是根号分值，不过发现「保证 \(y\le x\)」，意味着修改是全局修改，不用对每个块都开一个标记数组 .

但是区间查询跑完所有标记是 \(O(B^2)\) 的，非常慢，于是考虑维护标记标记的前后缀和，遍历标记时只用枚举 \(i\) 不必枚举 \(j\) .

卡常卡不动了，rk3，呜呜 .

可以直接把 \(B\) 设为 \(L\) .

预处理 \(O\left(n\right)\)，修改 \(O\left(\min\left(B, \dfrac{n}{B}\right)\right)\)，查询 \(O\left(L + C\right)\) .

Luogu Submission .

P5046 [Ynoi2019 模拟赛] Yuno loves sqrt technology I

最卡常但是也是最喜欢的一个题！不过两者没有联系 .

首先从拆贡献入手：整块与整块之间，散块和整块之间，两个散块之间，散块和自己 .

思考过程太抽象了我还是不引导性讲解了 .

设 \(pre_{i}\) 为 \(i\) 所在块的左端点到它的逆序对个数，\(suf_{i}\) 右端点，这样不用 BIT，\(sum_{i, j}\) 表示块 \(i\sim j\) 的逆序对数量 . 然后是一个对于卡常相当重要的 \(f_{i, j}\) 表示 \(1\sim j\) 中的所有数与块 \(i\) 之间的逆序对数。（换成这个写法才过的，拜谢 @crimson000）

预处理时，对每个块内排一遍序，因为归并排序可以求逆序对数，这样方便归并 . \(pre\) 和 \(suf\) 是容易处理的，\(f\) 考虑在对整个数列排序后进行归并排序 . \(sum\) 可以直接拼起来，即 \(sum_{i, j - 1} + sum_{i + 1, j} - sum_{i + 1, j - 1}\) 加上 \(i\) 和 \(j\) 之间的贡献，可以用 \(f\) 求 .

回到查询：

• 整块与整块之间：\(sum\) 已经预处理出来了 .
• 散块和整块之间：利用 \(f\) 数组差分求出 .
• 两个散块之间：归并排序 .
• 散块和自己：\(pre\) 和 \(suf\)，不过左右端点在同一个块时要归并一下去除多余贡献 .

虽然分讨但是没有太复杂的细节，每个地方都有一定趣味，更趣味的是题意非常典 .

预处理 \(O\left(n\log L + Cn + C^2 \right)\)，查询 \(O\left(L + C\right)\) .

Luogu Submission .