P5354 [Ynoi Easy Round 2017] 由乃的 OJ
紫，树链剖分+线段树。
树上的位运算，由于每一位独立可以考虑按位拆解，分别计算每一位为 0 或 1 的情况。选 0 更优肯定选 0，否则若能选 1 则选 1。位运算用树剖后线段树维护。这里注意三个位运算混一起的时候是没有交换律的，但有结合律，所以路径正着走和倒着走结果完全不一样，因此线段树要维护左进0/1和右进0/1两种情况。例如起点 \(\to\) lca 需要左进，而终点 \(\leftarrow\) lca 需要右进（从lca进）
如果真的每位单独算复杂度还是爆炸，关键在优化 k 上。我们想让 k 位一起算，考虑两个区间如何正确合并。
举个例子，左侧进0分两种情况处理：
- 左块左进0右出1的位，右块按左进1处理
- 左块左进0右出0的位，右块按左进0处理
参考题解，k 位合并参考 deepseek，细节很多，看代码注释。
P4688 [Ynoi Easy Round 2016] 掉进兔子洞
紫，莫队+bitset。
参考题解，有个 trick 是既然 bitset 无法存具体数值，就把具体数值拆成若干个 1 存在 bitset 里，而且有个好处是取 min 是且运算，取 max 是或运算，非常快。注意我们开不起 1e5 个长度为 1e5 的 bitset，可以把值域分成多次来做，这里选用了 20000 一组，而且在存的时候小心细节。实现难度不大。