題目傳送門：CF1924F

還是第一次見這種勢能題。
先把交互庫的回答轉成 \(0,1\) 表示答案是否在這個區(qū)間中。
首先把題目轉化一下，對每個位置 \(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\) 的末尾出現(xiàn)連續(xù) \(3\) 個一樣的數(shù)他就不可能是答案了。
顯然對于每個 \(S_i\) 我們只需要維護他是否已經(jīng)死了以及他的最后兩位。
考慮給每個串附一個勢能，一個局面的勢能為所有串的勢能之和。那么對于已經(jīng)死了的串勢能就是 \(0\)；由于對稱性，00 和 11 的勢能應該是一樣的，不妨設勢能為 \(1\)；同樣的，01 和 10 的勢能也是一樣的，假設為 \(x\)（目前還不確定）。
那么初始局面的勢能 \(E_{begin}\) 最多是 \(nx\)，有解的必要不充分條件為最終局面的勢能 \(E_{end}\in [2,2x]\)。
不妨列一下對于不同種類的串，在末尾加一個 0 或 1 之后勢能的變化：（\(E\) 代表原勢能，\(E_0\) 代表加 0 之后的勢能，\(E_1\) 同理）

我們希望每次詢問之后勢能可以穩(wěn)定減少從而保證操作次數(shù)，那么有兩種基本想法：每次穩(wěn)定減少一個值或者每次乘上一個值。前者不太可能，我們考慮后者。
那么首先我們需要讓任意串的 \(\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\)。
也就達到了理論最優(yōu)操作次數(shù) \(\log_{\frac{2}{x}}(E_{begin})-\log_{\frac{2}{x}}(E_{end})\)。

我們現(xiàn)在考慮如何選擇每次詢問的區(qū)間能使得 \(E_0\) 和 \(E_1\) 足夠接近。
注意到對于那些已經(jīng)死了的位置勢能不再變化可以不去管他，設 \(\Delta E_i\) 表示選擇前綴 \(i\) 進行詢問，\(E_0-E_1\) 的值，\(\Delta E_{\emptyset}\) 則表示詢問空集（即詢問的前綴不包含任何沒死的位置，雖然可能不存在這樣的前綴，但這并不影響我們之后的分析），顯然 \(\Delta E_n=-\Delta E_{\emptyset}\)，因為每個串的勢能都取反了。
考慮 \(i\) 變成 \(i-1\) 的時候，最多只有一個串的 \(E_0-E_1\) 發(fā)生了變化/取反，所以 \(|\Delta E_i - \Delta E_{i-1}|\) 是 \(O(1)\) 的。
如果 \(E_n=0\) 那么我們直接詢問整個串即可，否則由于 \(\Delta E_n=-\Delta E_{\emptyset}\)，函數(shù)圖像必過 \(x\) 軸，又因為相鄰兩點的變化是 \(O(1)\) 的，所以我一定可以找到一個 \(i\) 使得 \(\Delta E_i=O(1)\)，也即詢問前綴 \([1,i]\) 就滿足我們的需求。

最后我們再進一步分析一下初始的勢能 \(E_{begin}\)。
設第一次詢問的區(qū)間為 \(A\)，第二次詢問的區(qū)間為 \(B\)，設 \(a\) 為同時屬于 \(A,B\) 的位置個數(shù)加上同時不屬于 \(A,B\) 的位置個數(shù)，\(b\) 為屬于 \(A\) 但不屬于 \(B\) 的位置個數(shù)加上屬于 \(B\) 但不屬于 \(A\) 的位置個數(shù)。那么如果第一次和第二次的回答相同，初始勢能為 \(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]\) 即可達到這個下界。

我們最終的最壞操作次數(shù)大約是 \(\log_{\frac{2}{x}} n+C\)，其中 \(C\) 是一個小常數(shù)，但是由于 \(\frac{4}{1+\sqrt{5}}\approx 1.236\)，而 \(\log_{1.236} N=54\) 遠小于 \(\log_{1.116} N = 104\)，所以是隨便過的。