Gates to Another World

larsr · 2026-07-20 15:49:41 · 题解

爆标做法。

显然要时光倒流。

其它题解都是把一个区间拆成 O(n) 个区间，实际上可以只拆成 2 个区间。对于区间 [l,r]，设 d 是 l,r 最高的不同位，得到 mid=l\ \text{or}\ (2^d - 1)，两个区间就是 [l,mid] 和 [mid + 1,r]。每个区间内部都是连通的，正确性读者自证不难。那么区间数就是 O(m) 的。

放到 trie 树上合并，发现边数只有 O(nm) 条。

然后用并查集维护区间之间的连通关系，复杂度 O(nm)。