A 箱庭迷宫 题解

转化后问题变成：

次询问，每次给出 ，查询 ，保证 。

正常有个暴力我们可以预处理：，但是这样需要 的时空复杂度。

当然还有个暴力是每次询问的时候直接 枚举 。

两个暴力结合一下：设一个阈值 ，低位（小的 位）预处理 ，大的位置每次询问暴力跳。预处理 在 中有的高位发生改变了就停。查询的时候每次找到 第一个高位改变的位置，然后高位的贡献固定，低位的攻下预处理过了，复杂度是 。认为 同阶，平衡后复杂度是 ，因为空间也是 ，实际上 取小一点，比如 足以通过。