璀璨星空1讲的喵。
下令 \phi=1.618=\dfrac{1+\sqrt{5}}{2}。
我们将给出一个询问复杂度 \Theta(\log_{2/\phi} n) 复杂度的做法，并证明任何做法至多比该做法询问次数少 1，在本题中，这个做法需要 54 次，远远优于原题的 114 次。原题是 3.5k 那这个做法是不是应该评 4.0k（
我们考虑一个抽象的问题，该问题与原问题等价：
选手可以给交互库一个区间 [l,r]，交互库对该询问给出一个 0/1 的应答，代表本次交互库的选择。交互库同时维护序列 \{S\}，表示 S_x 说谎情况，每次交互库若选择 0，即往 [l,r] 后面加个 0，代表若答案 \in[l,r]，则交互库说谎了，反之同理；反之同理。
当出现 000/111 子串时，这个答案就死了。
我们为末尾子串 01,10,11,00 赋个势能。
当前状态的势能 E 被定义为每个串的势能之和。
每次交互库可以选择返回 0/1，设 E_0 和 E_1 分别为交互库返回 0/1 后的势能。
我们不妨设 H_{01}=H_{10}=x,H_{11}=H_{00}=1
显然一个串死了权值就是 0。
转移表：
| 末尾字符/加入字符 |
00 |
01 |
10 |
11 |
| 0 |
死了 |
x |
1 |
x |
| 1 |
x |
1 |
x |
死了 |
接下来我们分析 E_0+E_1 的结果。
读者可以自行枚举每种情况加入 0/1 后的权值。
|
00 |
01 |
10 |
11 |
| \dfrac{E_{0}+E_{1}}{E} |
x |
\dfrac{(1+x)}{x} |
\dfrac{(1+x)}{x} |
x |
我们希望 x=\dfrac{(1+x)}{x}，自然解得 x=\phi（显然 x>0）
我们分析到：E_0+E_1=\phi E，我们作为交互库，希望 E 尽可能大，所以 \max(E_0,E_1)\geq \dfrac{\phi}{2}。
也就是说，每次询问我们至多使得 E 减少 \dfrac{\phi}{2} 倍。
注意到我们在当前状况下可以找到解的必要条件是：E_{\text{final}}\leq2\phi。
初始势能至少为 \dfrac{n}{2}(1+\phi)=E_{\text{begin}}，这是因为：显然第一次询问可以直接回答你喜欢 0 还是 1，第二次询问我们考察：显然序列在第二次询问与第一次询问中，恰属于一个询问的部分和它的补集，这分别对应我们回答 0/1，其大小的较大值应当 \geq \dfrac{n}{2}，我们便直接返回该较大值所对应的 0/1，显然该部分使得势能 \geq \dfrac{n}{2}(1+\phi)。
也就是说，任何程序至少需要使用 \log_{2/\phi}(E_{\text{begin}})-\log_{2/\phi}(E_{\text{final}})=\log_{2/\phi}{n}-O(1) 次询问才能得到答案。
具体实现上，我们仿照上述过程，每次找 E_0 与 E_1 最接近的部分询问，并维护上述字符串集合 S 即可，可以证明，每次我们找到的 E_0-E_1=O(1)。
具体证明考虑以下事实：当询问区间为 \varnothing 时，记 E_0,E_1 分别为 E_{0,0},E_{0,1}，同理，当询问区间为 [1,n] 时，记 E_0,E_1 分别为 E_{n,0},E_{n,1}，注意到 E_{i} 单调不增/不减，且 E_{0,0}=E_{n,1},E_{n,0}=E_{0,1} 每次 i\to i+1 的过程只会让势能变化 O(1)，故取曲线的交点，则此处 E_0-E_1=O(1)，则 \max(E_0,E_1)=\dfrac{2E}{\phi}+O(1)。
AC Code: https://codeforces.com/contest/1924/submission/276915671