题解 P7128 【「RdOI R1」序列(sequence)】

Thomas_Cat · 2020-12-19 21:58:57 · 题解

赛后口胡题解：

Ps：可能受了验题影响因此可能代码像std就不放了（

对于该题，我们知道的条件是：

• 有一课二叉树，节点数为 2^p-1，其中 x_i,x_{2i},x_{2i+1} 的关系很容易理解：父亲和左儿子右儿子。

• 从上面的到：在该二叉树中对于节点 j，可与 2j,2j+1交换位置，使其编号与值相等。

因此我们的处理方法如下：

• 找到 x_i

• 找到 x_i,x_{x_i} 的 LCA

• 用儿子交换到 x_{x_i}

• 从 x_q 处理至 x_1

口胡完毕（