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

🔗 CF2178E Flatten or Concatenate

rating: 1969

Problem Statement

題目簡述

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

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

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

Constraints

約束條件

  • nn (1≤n≤1051 \le n \le 10^5)。
  • 隱藏陣列中的元素 1≤ai≤2301 \le a_i \le 2^{30}。
  • 詢問次數限制：300300。

思路：二分搜尋

核心觀察

操作對總和的影響

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

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

分割點的意義

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

  1. 來自 Concatenate 操作：

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

  2. 來自 Flatten 操作：

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

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

二分搜尋策略

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

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

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

複雜度分析

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

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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
 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
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()