前言

这篇主要参考了 JOISC 官方题解,算法 2 和 3 两部分可以看作是官方题解的翻译+解释,不过最后的通信量分析和原题解有些出不一样,有兴趣的朋友可以自行翻阅原题解。
这篇文章前前后后咕了 4months,可能中间有一些错误或者不严谨的地方,欢迎批评指正。
(应该是全网第一篇?)
ps: 算法 2 的关于 $\alpha$的那一块还有些问题,等我搞清楚再来补吧。

简要题意

现在有一个长为 $N$ 的排列 $a$ 和两个数 $L,R$。Anna 需要回答 $a$ 在区间 $[L, R]$中的最小值。
但是,Anna 只知道 $N,L,R$,与此同时,还有一个人 Bruno,他只知道 $a$ ,但不知道 $L$ 和 $R$ 。
Anna 和 Bruno 之间可以以发送比特的方式通信。其中,Anna 只能发送不超过 18 个比特,Bruno 需要最小化发送的比特数。AC 目标是 bruno 发送的比特数 $\leq 300$
$N \quad 1e6$
中间还有一些部分分,具体可自行参考题面

算法 0

我会暴力!Bruno 直接把 $a$ 全发给 Anna!
通信量:
$$
Anna:0 \quad bits \\
Bruno:Nlog_{2}N \quad bits
$$
期望得分:$1pts$。

算法 0.5

Anna 可以把 $L$ 和 $R$ 的最高 9 位发给 Bruno,这样 $L$ 和 $R$ 的取值范围大小就缩小到了 $\frac{N}{2^{9}}$。
Bruno 把 $L$ 和 $R$ 的波动范围内的所有数+ $L$ 和 $R$ 之间的所有数的 min 发给 Bruno。
通信量:
$$
Anna:18 \quad bits \\
Bruno:\frac{N}{2^{9}}·2·log_{2}N \quad bits
$$
期望得分:$10pts$。

算法 1

可以发现 Bruno 发送数字是非常愚蠢的行为,因为我们只需要知道相对大小关系。甚至,我们连全部的相对大小关系也不需要知道,我们只要区间的最小值。
笛卡尔树恰好是一种能很好体现区间最小值的树形结构。
我们一时半会儿想不到如何直接传输它的办法,然而它还有另外一种表现形式——单调栈,把弹栈看成 $0$,压栈看成 $1$,就可以在 $2N-1$ 个比特内传输长为 $N$ 的序列的单调栈,在 Anna 处再还原出最小值即可。
通信量就是把算法 $0.5$的 $log_{2}n$ 换成 2。
期望得分:$18pts$。

算法 2

笛卡尔树有这样一个性质:区间 $[L,R]$的最值正好是节点 $L$ 和节点 $R$ 的 LCA。
现在问题可以转化为:Anna 知道两个编号,Bruno 知道一棵树,Anna 需要回答这两个编号在 Bruno 手中的树上对应的节点的 LCA 的编号。
笛卡尔树上的一个节点同时也可以表示一段区间,如果 Bruno 向 Anna 发送笛卡尔树重心对应的区间端点,那么 Anna 可以返回 l,r 是否完全包含于 Bruno 提供的 $[L,R]$,若是,那么所求 LCA 在重心对应子树内,反之则不是,答案必不在重心对应子树内。
考虑这么做的效率,定义效率为一次询问-回答后的答案范围/此前的答案范围,初始答案范围是整棵树。
假设整棵树大小为 $V$ ,当前重心为 $k$ ,相连的 $3$ 棵子树的大小分别为 $a$ , $b$ ,$c$ ( $a+b+c+1=V$ , $a$ 为整棵树除开 $k$ 子树外的部分 $b$ , $c$ 为 $k$ 子树内的树)。
因为我们不关心 $b$ 和 $c$ 的顺序,且其实可以对重心的子树进行同样的询问,所以此处 a,b,c 等价,不妨设 $a\geq b\geq c$。
在 1 次询问之后,可能只剩下 $a$ ( $k$ 子树外的部分),也可能剩下 $k$ 的子树,大小为 $b+c+1$。
若剩下的是 $a$ ,则效率不劣于 $0.5$ (重心性质)。
若剩下的是 $b+c+1$ ,那么 Bruno 向再询问一次,剩下的部分大小就不会超过 b(重心性质)。
对于第二种情况,可以设 $\alpha$满足 $$\alpha V\geq b+c+1 或\alpha^{2} V\geq b$$,那么效率一定不劣于最小的 $\alpha$。
假设 $\alpha$不满足上述条件,那么
$$
\alpha V\leq b+c+1 且\alpha^{2} V\leq b \\ \Rightarrow V\geq a+\alpha V\geq b+\alpha V \geq V \times (\alpha +\alpha^{2}) \\ \Rightarrow \alpha \geq \frac{\sqrt{5}-1}{2}
$$。而且 $\frac{\sqrt{5}-1}{2}$是 $\alpha$的一个合法值。
所以效率不会劣于 $\frac{\sqrt{5}-1}{2}$。
PS:这个东西的实质是二叉树的边分治,所以我们同时也得到了二叉树边分治复杂度的 log 的底数是 $\frac{\sqrt{5}-1}{2}$。
但请注意,这个分析是基于同时分析两步,所以最后一步的效率还是可能被卡到 $\frac{2}{3}$。
$18$ 次询问用完之后对于剩下部分用算法 1 中提到的方法发送全部数字。
通信量:
$$
Anna:18 \quad bits \\
Bruno: 大约 870 bits(来自 JOISC 本题解说员的估计)
$$
期望得分:$80pts$。

算法 3

前言:我也不知道这东西是怎么想出来的,反正很强就是了。
考虑一个构造,最开始在数列里选择一个位置, $1$ 个元素显然也是一个长度为 $1$ 的区间,命名其为 $I_{1}$。然后每次观察当前区间的左边和右边的数,把大的那个数纳入当前区间,形成一个比之前长度多 $1$ 的区间。这样依次得出的区间命名为 $I_{2},I_{3}……I_{n}$。
如果最开始选择的位置在询问的 $[L,R]$内,那么会有一个有趣的性质:
对于任意 $i$ ,必有以下之一:
1.$[L,R] \in I_{i}$。
2.$I_{i}$中的最小值即为所求。
3.$I_{i}$中不包含所求。
二分,初始值为 $[1,n]$。每次 Bruno 发送 $I_{mid}$的左端点和右端点,Anna 回答 $[L,R]$是否包含于 $I_{i}$,最终 Bruno 可以发送二分边界 l 对应的 $I_{l}$的区间最小值和 $I_{r}-I_{l}$部分的所有数的单调栈,Anna 可以据此得出所求。
这样做的话,效率 (同算法 $2$ 定义) 显然是 $0.5$ 。
但是,Bruno 不知道询问的 $[L,R]$,他无法保证自己选择的初始位置在询问的 $[L,R]$内。
如果我们在线段树上找到最小的包含 $[L,R]$的区间,那么这个区间的 mid 一定是在询问的 $[L,R]$内的。
Anna 可以直接发送询问区间对应的线段树节点的深度,然后 Bruno 二分前文中提到的 $L,R$,最后如前文所说发送内容。
分析这样做的通信量:
1. 如果区间足够小 (区间长 $\times 2$$\leq 300$),直接发送整个区间的单调栈。
2. 根据第一点,我们可以只考虑询问区间长度大于 $150$ 的询问,在 $n=1000000$ 的线段树上,最小的包含 $[L,R]$的区间深度不会超过 $13$ ,故 Anna 发送线段树节点深度的通信量不超过 $4bits$ 。剩下的 $14$ 个 $bits$ 可以使答案范围缩小 $2^{14}$,Bruno 通信量 (最坏情况:深度为 $0$ ,二分 $14$ 次):每次二分时 Bruno 发送 $I_{mid}$的左端点和右端点,每次需要 $40$ bits,求得 $560 bits$ 左右,最后发送单调栈的通信量是 $1000000/2^{14}\times2$约为 $122bits$ 左右。总通信量在 $700bits$ 左右,需要进一步优化。
可以发现,同时发送左端点和右端点是没有必要的,因为 Anna 根据已二分的次数可以判断当前 $R-L$的值,只需要发送左端点,$560bits \to 280bits$。
每次发送左端点都需要 $20bits$ ,试图在这一点上优化。
感性的理解,每次区间的范围会越来越小,而区间一定包含我们在构造时选择的那个” 原点”,所以区间的左端点每次二分后范围会减少一半,每次二分 Bruno 发送左端点时都可以比前一次少发 $1bit$ 。由等差数列求和可得,最差情况 (深度为 $0$ ,二分 $15$ 次):第一部分用去 $195bits$ , 第二部分用去 $62bits$ 左右,总和不超过 $260bits$ 。

分类: 文章

0 条评论

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

*

code