【解题报告】JOISC 2019 Day4

「JOISC 2019 Day4」蛋糕拼接 3

若现在已经选出了若干元素，为了使其价值尽量大，一种最优方案是按 $C$ 排序放置，这样后面那项就只有：

$$ 2\times (\max C_i-\min C_i) $$

考虑枚举 $\max C_i$ 是谁，可以发现 $\min C_i$ 的选择是单调的，也就是越大的 $\max C_i$ 不会选择更小的 $\min C_i$。直接决策单调性，套个主席树就行了。复杂度 $\mathcal{O}(n\log^2 n)$。

「JOISC 2019 Day4」合并

显然可以转变为：没有一个子树内颜色是“封闭”的。首先可以找出所有断后不合法的边，断掉后得到若干连通块，缩点之后再将边连回来，这样的树与原来等价，可以看作每个点颜色不同。

操作次数下界是叶子个数除 $2$ 上取整。

「JOISC 2019 Day4」矿物

首先可以使用 $2n$ 次操作，将元素划分为两个集合 $A,B$。

然后考虑朴素的二分，对每个 $B$ 可以用 $\log$ 次确定对应的 $A$。套一个整体二分，但这样过不了。

考虑不从 $0.5n$ 处二分，设这个常数是 $p$，实际上操作次数是：

$$ F(n)=(1+p)n+F(pn)+F((1-p)n) $$

不知道怎么解出 $p=\dfrac{3-\sqrt{5}}{2}$ 的时候最优，注意 query 操作不能撤销，不然常数就爆炸了，正确的做法是在整体二分的时候，记录一下当前区间的 $A$ 元素是全部都在集合中，还是全都不在集合中。