蒟蒻 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)，好像就做完了。
似乎处理幂的时候还需要用光速幂，不过这应该是基本素养了。