CF1935

· · 个人记录

CF1935

E

Solution

首先考虑每一对 (x_i,y_i)，将其二进制分解。

其中 x_i 和 y_i 的公共前缀一定会对答案产生贡献，这部分可以用 st 表维护区间 or，计为 d。

对于剩下的部分，考虑 y_i 的第 j 位为 1，由于 or 的性质，我们可以对 y_i 的每一位分别考虑其贡献 2^j 还是 2^j-1。

从高位到低位贪心，设 c_j 表示询问区间内有多少个 y_i 的第 j 位为 1 且不在与 x_i 公共前缀内，若 d 的第 j 位为 1，则令 c_j 额外加上 1。

## F #### Solution 对于第 $i$ 个点，所加的边一定是度数减 $1$ 条。 我们一定是尽可能加代价为 $1$ 的边，定义 $mx$ 为与 $i$ 相连的连通块内编号最大的点，$mi$ 为编号最小的点，有如下构造方案。 1. 若 $i=1$ 或 $n$，则所有连通块在可行时连 $mx \rightarrow mx+1$。 2. 若对于所有连通块 $x$，不存在 $mi_x<i<mx_x$，即所有连通块编号在 $i$ 两侧，我们将其分为左右集合，对于左集合右集合内部，用方案 $1$，再连边 $i-1 \rightarrow i+1$。 3. 若对于所有连通块 $x$，存在 $mi_x<i<mx_x$，则将所有 $mx_x < i $ 分为左集合，其余分为右集合，对于左集合，连 $mi \rightarrow mi-1$，右集合，连 $mx_x \rightarrow mx_x+1$。由于 $1$ 可能在左集合，这样会连一条边。我们找到右集合 $mi$ 最小值，连 $mi \rightarrow mi-1$。容易证明这样不会连成环。 $mi,mx$ 可以用换根 dp 求出。