题解：CF840E In a Trap

· · 题解

cnblogs

前言

做法和别的题解基本一样，提供一个去 \log 的方法。

解法

考虑根号算法，n<256^2，256\approx O(\sqrt n)。

将 path(x,y) 从下往上每 256 个分一块，这样块内 dis(i,y) 二进制前 8 位相同。

称 S(x) 表示从 x 开始往上 256 个点的集合。

预处理出 f_{x,i}=\max\limits_{y\in S(x)}\{a_y\oplus dis(x,y)\oplus (256i)\}，就能快速查询。\gdef\dfloor#1#2{\Big\lfloor\dfrac{#1}{#2}\Big\rfloor}

先处理 f_{x,i} 的前 8 位， \max\limits_{y\in S(x)}\{\dfloor{a_y}{256}\oplus i\}，需要 DS 维护。

维护方法

dfs 的过程中，DS 动态维护 S(x) 中的点的 a 的前 8 位。

称 p_x 为 x 的 256 级祖先（可能不存在）。

dfs 进入 x 时，加入 \dfloor{a_x}{256}，若 p_x 存在则删除 \dfloor{a_{p_x}}{256}。

dfs 退出 x 时，删除 \dfloor{a_x}{256}，若 p_x 存在则加入 \dfloor{a_{p_x}}{256}。

这样 DS 里面肯定是 S(x) 中的点的 a 的前 8 位。

发现加入删除总次数是 O(n) 的。

然而查询次数是 O(n\sqrt n) 的。

直接用 trie 总复杂度就 O(n\sqrt n\log n) 了。

考虑根号平衡，修改 x 遍历 i=0\sim 255，将 x\oplus i 加入删除。

需要支持 O(1) 加入删除 0\sim 255 的数，O(1) 查询最小值。

注意到 256=4\times 64，用 4 个 unsigned long long 压位即可。

设 g_{x,i}=\max\limits_{y\in S(x),\lfloor{\frac{a_y}{256}}\rfloor=i}\{dis(x,y)\oplus (a_y\operatorname{bitand} 255)\}。

若 f_{x,i} 前 8 位为 v，那么后 8 位就是 g_{x,v\oplus i}。

时间复杂度 O(n\sqrt n+q\sqrt n)，空间复杂度 O(n\sqrt n)，unsigned short 卡空间。

Submission