Ptz Winter 2018. Day 3.

问 $0$ 和 $\frac{n}{2}$ 然后知道在那一边，然后二分。

还可以做到更强。

维护 deque。复杂度 $O (nm lo g n)$ 。

记 $b_{u} = \oplus a_{i}$ ，等价于 $b_{u}$ 和 $b_{v}$ 异或 $x$ 。连边，连通块内 $\oplus b_{i}$ 不变，等价于最大化划分为异或和为 $0$ 的连通块个数。相同的可以直接两两一组。剩下的 $O (3^{15})$ 计算。

等价于任意一个 $d_{u} = k \geq 3$ 的点，至少有 $k - 1$ 个儿子的子树有值。以一个 $d_{u} \geq 3$ 的点为根，可以保证子树外至少有一个。

Q4805 的构造部分对任意图的通解。

对于根节点挂多条链，在每条链的链底维护排好序的一部分，把根节点的值插入排序。如果根节点就是自己，就随便扔到一个链最后，当重新回到根的时候必然做完了这条链，多 $n$ 次。

从下往上扔叶子，在最下面的分叉之前，每条链独立。最多做 $lo g n$ 次。

segment tree beats

两个相邻整行都没有障碍，则一定有上边点数乘下面点数的贡献，然后缩起来。剩下 $O (n^{2})$ 个点，bfs。

从小往大贪，每个连通块有度数限制。

Quartz 4