杂题题解 3

[NOI Online 2021 提高组] 岛屿探险

对于 \((a_i \oplus c_j)\leqslant \min(b_i,d_j)\),考虑拆掉 \(\min\)。当 \(b_i\geqslant d_j\) 时,为 \((a_i \oplus c_j)\leqslant d_j\),只需在 \(a_i\) 的可持久化 \(01\ Trie\) 上二分即可。当 \(b_i< d_j\) 时,为 \((a_i \oplus c_j)\leqslant b_i\),和刚才的情况是对称的,在 \(c_j\) 的 \(01\ Trie\) 上二分,打标记子树加来实现每个位置对询问的贡献。对位置和询问按 \(b_i\) 或 \(d_j\) 排序后 \(CDQ\) 分治即可,复杂度为 \(O(n\log^2 n)\)。

[NOI Online 2021 提高组] 岛屿探险

上一篇:NOI Online题解


下一篇:【DBCA -SILENT】静默安装之rac数据库安装