题解-Ynoi

蒟蒻 zcr 的 Ynoi 记录&简略题解

[Ynoi2016] 这是我自己的发明（2020-08-03）

把询问拆成至多四个部分然后跑树上莫队。

[Ynoi2016] 掉进兔子洞（2020-08-08 18:29）

莫队的时候用一个biset来维护并集。注意把询问拆成几个部分否则会爆空间。

[Ynoi2010] Fusion tree（2021-03-31）

01 trie 板子题。

[Ynoi2019 模拟赛] Yuno loves sqrt technology III（2021-03-31）

分块，预处理块 \(i\) 到块 \(j\) 的答案，即为 \(ans\)，然后考虑散块。预处理每种颜色的位置放在 vector 里，然后考虑散块中出现的颜色有没有出现 \(ans\) 次，有就将 \(ans\) 加一，然后继续判断。容易得到这样至多判断 \(O(B)\) 次，\(B\) 是块大小。取 \(B=\sqrt{n}\) 即可。

[Ynoi2015] 盼君勿忘（2021-07-01）

考虑现在有一个长度为 \(n\) 的序列，然你在多项式复杂度内求出答案。考虑每种不同的颜色 \(k\)（暂且叫颜色）的贡献，即它在多少不同的子序列中出现。从反面考虑，答案即为 \(2^n-2^{n-cnt_k}\)。它的贡献即为 \(k(2^n-2^{n-cnt_{k}})\)，所有的贡献即为 \(\sum_{t=1}^{n}s_t(2^n-2^{n-t})\)，其中 \(s_t\) 代表出现 \(t\) 次的数的和。

然后我们使用 Ynoi 中常见的根号分治，出现次数大于 \(\sqrt{n}\) 的直接暴力统计，我们要求的即为 \(\sum_{t=1}^{\sqrt{n}}s_t(2^n-2^{n-t})\)。

再使用另一个 Ynoi 中常见的技巧莫队，维护 \(s_t\)，好像就做完了。

似乎处理幂的时候还需要用光速幂，不过这应该是基本素养了。

[Ynoi2009] rla1rmdq

首先对序列分块，考虑记录每个块的答案。我们发现如果一个点跳到了一个这个块内其他点之前跳到过的节点，那么这个点就没有意义了，可以删去。所以我们只会遍历一遍整课树，总共有 \(\sqrt{n}\) 个块，总时间复杂度为 \(O(n\sqrt{n})\)。考虑散块修改，查询，可能会用一些已经被删掉的点，所以我们直接重构这个块。注意一个事实，我们跳到根了之后就不会再修改某个块，所以这样做的复杂度不变。由于打了懒标记，所以我们不能暴力向上跳，其实只要树剖/倍增就可以做到全局 \(O(n\log n)\)。

考虑具体实现，我们可以开 \(\sqrt{n}\) 个 bitset 维护每个点是否被跳到过。对于每个块维护两个信息，一个是块内答案，一个是可能成为答案的点，后者放到栈里。

总时间复杂度 \(O((n+m)\sqrt{n}+n\log{n})\)，空间复杂度 \(O(n\sqrt{n})\)。

[Ynoi2019 模拟赛] Yuno loves sqrt technology II

莫队二次离线板子，最后我们需要 \(O(1)\) 查，所以使用根号分治平衡复杂度。

[Ynoi2008] rrusq

离线扫描线，考虑每个点最先在哪个矩形出现，这个可以在2dt上打标记实现。然后考虑查答案，发现是个区间加单点查，换成单点加后缀查分块平衡一下复杂度即可。大概是 \(O(q\sqrt{n})\)。