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

🔗 ABC388G Simultaneous Kagamimochi 2

Problem Statement

題目簡述

有 NN 個麻糬依大小非遞減排列，第 ii 個大小為 AiA_i。
若一個麻糬大小至多為另一個麻糬大小的一半，就可以把較小者放在較大者上方，組成一個鏡餅。
給定 QQ 個區間詢問 (L,R)(L, R)，每次只能使用第 LL 到第 RR 個麻糬，求最多能同時組成幾個互不共用麻糬的鏡餅。

Constraints

約束條件

  • 2≤N≤2×1052 \leq N \leq 2 \times 10^5
  • 1≤Ai≤1091 \leq A_i \leq 10^9
  • Ai≤Ai+1A_i \leq A_{i+1}
  • 1≤Q≤2×1051 \leq Q \leq 2 \times 10^5
  • 1≤Li<Ri≤N1 \leq L_i < R_i \leq N
  • 所有輸入皆為整數。

思路：貪心 + 二分搜尋 + 線段樹/稀疏表

本題和 EE 題類似，都需要求區間內的最大配對數。由於 KK 越大越難滿足條件，答案具有單調性，因此可以對每個詢問二分搜尋最大的合法 KK。但如果使用 O(K)\mathcal{O}(K) 的檢查函數做二分搜尋會超時，因此需要先預處理每個位置的配對需求，再利用該性質進行二分搜尋。

若區間 [L,R][L, R] 內可以組成 KK 對，則可以讓最小的 KK 個數和最大的 KK 個數配對。其中最小的 KK 個數為 [L,L+K−1][L, L + K - 1]，剩下只需要確認它們是否都能在區間內找到足夠大的配對對象。

關鍵觀察

因為序列已經排序，若某個數可以作為上層麻糬，那麼選更小的數作為上層只會讓配對更容易。因此檢查 KK 對時，只需要考慮區間內最小的 KK 個數。

但若最小的 KK 個數中有一個數無法直接配對成功，則會影響到後續的數，使後續的數需要往後遞移。因此其實只需要考慮最小的 KK 個數的右端點 L+K−1L + K - 1，以及 [L,L+K−1][L, L + K - 1] 中的最大間距 max⁡gap\max\text{gap} 即可。

  • 如果 L+K−1+max⁡gap>RL + K - 1 + \max\text{gap} > R，則說明往後遞移之後會超過範圍，也就是 KK 太大了，需要縮小。
  • 反之，若 L+K−1+max⁡gap≤RL + K - 1 + \max\text{gap} \leq R，則代表這 KK 對可以全部安排在區間內。

這裡的「間距」指的是：對於某個位置的麻糬，找到第一個大小至少為它兩倍的位置，並記錄兩者的距離。由於陣列已排序，所有位置的間距可以用雙指標在 O(N)\mathcal{O}(N) 時間內預處理出來。

這其實就是 EE 題方法二的 O(1)\mathcal{O}(1) 檢查思路：在 EE 題中，因為每次都只檢查整個序列最前面的 KK 個數，所以可以預處理「前綴最大間距」，讓檢查條件變成：

(K−1)+preMax[K−1]≤N−1(K - 1) + preMax[K - 1] \leq N - 1

也就是只要看最小的 KK 個數中最大的跨越距離，是否還能放進整個序列的右端。

而本題多了區間詢問 [L,R][L, R]，每次檢查的不再固定是整個序列的前綴，而是區間中的前 KK 個數 [L,L+K−1][L, L + K - 1]。因此不能只用一個前綴最大值陣列做 O(1)\mathcal{O}(1) 檢查，而要改成支援「任意區間最大值」的資料結構。

根據此思路，可以預先計算出每個位置與下一個符合條件的位置的間距，並使用線段樹或ST表維護區間內的最大間距。如此便可以在 O(log⁡N)\mathcal{O}(\log N) 時間內查詢區間 [L,L+K−1][L, L + K - 1] 內的最大間距，檢查函數為：

L+K−1+max⁡gap≤RL + K - 1 + \max\text{gap} \leq R

複雜度分析

  • 時間複雜度：O(N+Qlog⁡2N)\mathcal{O}(N + Q \log^2 N)
    • 預處理每個位置與下一個符合條件的位置的間距，並以此建立線段樹需要 O(N)\mathcal{O}(N) 時間。
    • 二分搜尋需要 O(log⁡N)\mathcal{O}(\log N) 次，在預處理後，每次檢查只需要查詢線段樹，時間為 O(log⁡N)\mathcal{O}(\log N)，故對於每個詢問，時間複雜度為 O(log⁡2N)\mathcal{O}(\log^2 N)。
  • 空間複雜度：O(N)\mathcal{O}(N)

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
from atcoder.segtree import SegTree

N = int(input())
A = list(map(int, input().split()))

# 計算下一個符合條件的位置
nxt = [0] * N
right = 0
for i in range(N):
    while right < N and 2 * A[i] > A[right]:
        right += 1
    nxt[i] = right

# 計算每個位置與下一個符合條件的位置的間距
gaps = [nxt[i] - i for i in range(N)]
seg = SegTree(lambda x, y: max(x, y), -float('inf'), gaps)  # 維護區間內的最大間距

Q = int(input())
queries = [list(map(int, input().split())) for _ in range(Q)]
for (L, R) in queries:

    def check(k):
        return L + k - 1 + seg.prod(L - 1, L - 1 + k) <= R

    left, right = 0, (R - L + 1) // 2
    while left <= right:
        mid = (left + right) // 2
        # 查詢 [L, L+mid) 區間內的最大間距
        max_gap = seg.prod(L - 1, L - 1 + mid)  # 0-based
        if check(mid):
            left = mid + 1
        else:
            right = mid - 1
    print(right)  # 求最大的合法配對數