Codeforces 🔵 CF2178E. Flatten or Concatenate

題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 CF2178E Flatten or Concatenate

rating: 1969

Problem Statement

題目簡述

這是一個互動題。
Dilhan 有兩個初始為 $[2^k]$ 的陣列 $a$ 和 $b$。他可以任意次數執行以下操作：

1. Flatten：選定一個陣列中的最大偶數元素 $x$，將其替換為兩個 $x/2$。
2. Concatenate：將 $a$ 和 $b$ 都更新為 $a+b$（陣列串接）。

最終 $b$ 被丟棄，$a$ 被隱藏，長度為 $n$。你可以進行最多 $300$ 次詢問，每次詢問區間 $[l, r]$ 的和。
目標是求出隱藏陣列 $a$ 中的最大值。

Constraints

約束條件

• $n$ ($1 \le n \le 10^5$)。
• 隱藏陣列中的元素 $1 \le a_i \le 2^{30}$。
• 詢問次數限制：$300$。

---

思路：二分搜尋

核心觀察

操作對總和的影響

• Flatten 操作：將 $x$ 替換為 $\dfrac{x}{2}, \dfrac{x}{2}$，總和不變。
• Concatenate 操作：將 $a, b$ 都變為 $a + b$，總和翻倍。

因此，最終陣列的總和一定是 $2^k$。

分割點的意義

我們可以透過二分搜尋找到前綴和等於 $2^{k-1}$ 的位置 $x$。這個分割點可能有兩種含義：

1. 來自 Concatenate 操作：

   • 陣列是由 $[1, x]$ 和 $[x+1, n]$ 兩個子陣列拼接而成。
   • 由於較短的區間使用 Flatten 操作的次數更少（因為 Flatten 只增加長度、不減少），所以最大值必定落在較短的區間。

2. 來自 Flatten 操作：

   • 這個區間是由某個陣列經過 Flatten 操作分裂而成。
   • 同樣地，較短的區間使用 Flatten 的次數更少，最大值也落在較短區間。

關鍵結論

無論是哪種情況，最大值一定位於長度較短的那一半區間中。

二分搜尋策略

基於上述觀察，我們可以採用以下策略：

1. 查詢或從前一輪的總和 $2S$，得到當前區間 $[l, r]$ 的總和 $S$。
2. 利用二分搜尋找到分割點 $m$，使得 $[l, m]$ 的和為 $\dfrac{S}{2}$。
3. 比較左右兩部分的長度，選擇較短的區間繼續處理。
4. 當區間長度為 $1$ 時，當前的總和 $S$ 即為該元素的值，也是最大值。

經過一輪二分後，最大值所在的區間長度至少縮小一半。因此最多經過 $O(\log n)$ 輪二分，就可以將區間縮小至 $1$。

複雜度分析

• 時間複雜度：$\mathcal{O}(\log^2 n)$
  • 每輪需要 $O(\log n)$ 次詢問來二分找分割點，共 $O(\log n)$ 輪，總計 $O(\log^2 n) \le 300$。
• 空間複雜度：$\mathcal{O}(1)$

---

Code

def query(l, r):
    print(f"? {l} {r}", flush=True)
    return int(input())

def answer(x):
    print(f"! {x}", flush=True)

def solve():
    n = int(input())

    l, r = 1, n
    s = query(1, n)
    while l < r:
        # 找到分割點 x 使得 [l, x] 的區間和 == [x + 1, r] 的區間和
        s //= 2
        left, right = l, r - 1
        while left <= right:
            mid = (left + right) // 2
            if query(l, mid) < s:
                left = mid + 1
            else:
                right = mid - 1
        # 此時 [1, left] 的區間和 == [left + 1, r] 的區間和
        # 根據兩個區間的長度判斷最大值的位置
        if (left - l + 1) <= (r - left):
            r = left
        else:
            l = left + 1
    answer(s)

if __name__ == "__main__":
    t = int(input())
    for _ in range(t):
        solve()

---

寫在最後

互動題的本地測試技巧

對於這類互動題，我們可以在本地撰寫一個 Judge 類別來模擬評測系統的行為。我們可以「劫持」原本用於與評測機通訊的 query() 和 answer() 函數，將它們重新指向本地 Judge 的對應方法。這樣一來，我們的程式碼可以在實際提交到評測系統之前，先在本地進行一定的測試和驗證。

Code with Judge

from random import randint, choice
from itertools import accumulate

DEBUG = False

class Judge:
    def __init__(self, n: int):
        self.n = n
        self.query_count = 0
        self.max_queries = 300
        self.array = self._generate_array(n)
        self.s = list(accumulate(self.array, initial=0))
        # print(f"[DEBUG] Generated array: {self.array}")
        
    def _generate_array(self, n: int):
        k = randint(1, 30)
        A, B = [1 << k], [1 << k]

        def flatten(arr):
            max_val = max(arr)
            idx = choice([i for i, x in enumerate(arr) if x == max_val])
            return arr[:idx] + [max_val // 2, max_val // 2] + arr[idx+1:]

        while len(A) < n:
            ops = []
            if max(A) > 1:
                ops.append('flatten_a')
            if max(B) > 1 and len(A) + len(B) + 1 <= n:
                ops.append('flatten_b')
            if len(A) + len(B) <= n:
                ops.append('concat')
            if not ops:
                k = randint(1, 30)
                A, B = [1 << k], [1 << k]
                continue
            op = choice(ops)
            if op == 'concat':
                new = A + B
                A = new[:]
                B = new[:]
            elif op == 'flatten_a':
                A = flatten(A)
            else:
                B = flatten(B)
        assert len(A) == n
        return A
        
    def query(self, l: int, r: int) -> int:
        assert 1 <= l <= r <= self.n
        self.query_count += 1
        assert self.query_count <= self.max_queries
        return self.s[r] - self.s[l - 1]
        
    def answer(self, x: int):
        print(f"[DEBUG] Answer: ! {x}")
        print(f"[DEBUG] Total queries used: {self.query_count}")
        
        if x == (ans := max(self.array)):
            print("[RESULT] Correct!")
        else:
            print(f"[DEBUG] Generated array: {self.array}")
            raise ValueError(f"Wrong answer: {x}, Correct answer: {ans}")

def query(l, r):
    print(f"? {l} {r}", flush=True)
    return int(input())

def answer(x):
    print(f"! {x}", flush=True)

def solve():
    n = int(input()) if not DEBUG else randint(1, 1500)
    
    if DEBUG:
        global query, answer
        judge = Judge(n)
        query = judge.query
        answer = judge.answer

    l, r = 1, n
    s = query(1, n)
    while l < r:
        # 找到分割點 x 使得 [l, x] 的區間和 == [x + 1, r] 的區間和
        s //= 2
        left, right = l, r - 1
        while left <= right:
            mid = (left + right) // 2
            if query(l, mid) < s:
                left = mid + 1
            else:
                right = mid - 1
        # 此時 [1, left] 的區間和 == [left + 1, r] 的區間和
        # 根據兩個區間的長度判斷最大值的位置
        if (left - l + 1) <= (r - left):
            r = left
        else:
            l = left + 1
    answer(s)

if __name__ == "__main__":
    t = int(input()) if not DEBUG else 10
    for _ in range(t):
        solve()