题目传送门：CF1924F
还是第一次见这种势能题。
先把交互库的回答转成 \(0,1\) 表示答案是否在这个区间中。
首先把题目转化一下，对每个位置 \(i\) 维护一个 01 串 \(S_i\) 表示：如果 \(i\) 是答案，那么当前交互库的每个回答是否是真话。即如果当前询问 \([l,r]\) 交互库的回答是 1 就往 \(S_i (i\in [l,r])\) 的末尾插入 1，在 \(S_j (j \in [1,l) \cup (r,n])\) 的末尾插入 0。
那么如果某个 \(S_i\) 的末尾出现连续 \(3\) 个一样的数他就不可能是答案了。
显然对于每个 \(S_i\) 我们只需要维护他是否已经死了以及他的最后两位。
考虑给每个串附一个势能，一个局面的势能为所有串的势能之和。那么对于已经死了的串势能就是 \(0\)；由于对称性，00 和 11 的势能应该是一样的，不妨设势能为 \(1\)；同样的，01 和 10 的势能也是一样的，假设为 \(x\)（目前还不确定）。
那么初始局面的势能 \(E_{begin}\) 最多是 \(nx\)，有解的必要不充分条件为最终局面的势能 \(E_{end}\in [2,2x]\)。
不妨列一下对于不同种类的串，在末尾加一个 0 或 1 之后势能的变化：（\(E\) 代表原势能，\(E_0\) 代表加 0 之后的势能，\(E_1\) 同理）
| 00 | 01 | 10 | 11 | |
|---|---|---|---|---|
| \(E_0\) | \(0\) | \(x\) | \(1\) | \(x\) |
| \(E_1\) | \(x\) | \(1\) | \(x\) | \(0\) |
| \(\frac{E_0+E_1}{E}\) | \(x\) | \(\frac{x+1}{x}\) | \(\frac{x+1}{x}\) | \(x\) |
我们希望每次询问之后势能可以稳定减少从而保证操作次数，那么有两种基本想法：每次稳定减少一个值或者每次乘上一个值。前者不太可能，我们考虑后者。
那么首先我们需要让任意串的 \(\frac{E_0+E_1}{E}\) 相同，否则交互库可以尝试尽可能地构造大的那种串，即 \(x=\frac{x+1}{x}\) 解得 \(x=\frac{1+\sqrt{5}}{2}\)。
此时由于每个串都满足 \(\frac{E_0+E_1}{E}=x\)，那么整个局面也必然满足 \(\frac{E_0+E_1}{E}=x\)，下面的 \(E_0,E_1,E\) 均指整个局面的，设 \(E'\) 为加入一个字符后局面的势能。
因为 \(E_0+E_1=xE\)，交互库肯定希望 \(E'\) 尽可能大所以他的回答会让 \(E'=\max(E_0,E_1)\ge \frac{x}{2} E\)，也就是说我们每次至多让势能变成原来的 \(\frac{x}{2}\)。
所以当 \(E_0\) 和 \(E_1\) 足够接近，那么我们每次就能让 \(E'\approx \frac{x}{2} E\)。
也就达到了理论最优操作次数 \(\log_{\frac{2}{x}}(E_{begin})-\log_{\frac{2}{x}}(E_{end})\)。
我们现在考虑如何选择每次询问的区间能使得 \(E_0\) 和 \(E_1\) 足够接近。
注意到对于那些已经死了的位置势能不再变化可以不去管他，设 \(\Delta E_i\) 表示选择前缀 \(i\) 进行询问，\(E_0-E_1\) 的值，\(\Delta E_{\emptyset}\) 则表示询问空集（即询问的前缀不包含任何没死的位置，虽然可能不存在这样的前缀，但这并不影响我们之后的分析），显然 \(\Delta E_n=-\Delta E_{\emptyset}\)，因为每个串的势能都取反了。
考虑 \(i\) 变成 \(i-1\) 的时候，最多只有一个串的 \(E_0-E_1\) 发生了变化/取反，所以 \(|\Delta E_i - \Delta E_{i-1}|\) 是 \(O(1)\) 的。
如果 \(E_n=0\) 那么我们直接询问整个串即可，否则由于 \(\Delta E_n=-\Delta E_{\emptyset}\)，函数图像必过 \(x\) 轴，又因为相邻两点的变化是 \(O(1)\) 的，所以我一定可以找到一个 \(i\) 使得 \(\Delta E_i=O(1)\)，也即询问前缀 \([1,i]\) 就满足我们的需求。
最后我们再进一步分析一下初始的势能 \(E_{begin}\)。
设第一次询问的区间为 \(A\)，第二次询问的区间为 \(B\)，设 \(a\) 为同时属于 \(A,B\) 的位置个数加上同时不属于 \(A,B\) 的位置个数，\(b\) 为属于 \(A\) 但不属于 \(B\) 的位置个数加上属于 \(B\) 但不属于 \(A\) 的位置个数。那么如果第一次和第二次的回答相同，初始势能为 \(a+xb\)，否则初始势能为 \(b+ax\)，交互库会选择其中大的那一个，而由于 \(x>1，\max(a,b) \ge \lceil \frac{n}{2} \rceil\) 故初始势能必定 \(\ge \lceil \frac{n}{2} \rceil (1+x)\)。我们分别询问 \([1,n]\) 和 \([1,\lfloor \frac{n}{2} \rfloor]\) 即可达到这个下界。
我们最终的最坏操作次数大约是 \(\log_{\frac{2}{x}} n+C\)，其中 \(C\) 是一个小常数，但是由于 \(\frac{4}{1+\sqrt{5}}\approx 1.236\)，而 \(\log_{1.236} N=54\) 远小于 \(\log_{1.116} N = 104\)，所以是随便过的。
)
：添加/删除用户)
)
