前言
这篇主要参考了 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 条评论