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

🔗 ABC381E 11/22 Subsequence

Problem Statement

題目簡述

給定一個只包含 1、2、/ 的字串，每次查詢一段子字串，要求在這段範圍內選出一個最長子序列，使它形如若干個 1、一個 /、再接上相同數量的 2。若無法選出任何合法的 11/22 字串，輸出 0。

Constraints

約束條件

$1 \leq N \leq 10^5$
$1 \leq Q \leq 10^5$
$S$ 是長度為 $N$ 的字串，且只包含 1、2、/
$1 \leq L \leq R \leq N$
輸入皆為整數或合法字元

思路：二分答案

一個合法的 11/22 子序列長度一定是奇數，並且可以寫成：

k \text{ 個 } 1 + 1 \text{ 個 } / + k \text{ 個 } 2

因此，問題轉化為：對每個查詢區間，找出最大的 $k$ ，使得區間內能依序選出 $k$ 個 1、一個 /、再 $k$ 個 2。答案即為 $2k+1$ 。

為什麼不能直接統計數量？

因為子序列仍然要維持原本順序。即使區間內有足夠多的 1、2、/，也必須存在一個 /，讓前面的 1 都能放在它左側，後面的 2 都能放在它右側。

為什麼可以二分答案

若 $k$ 可行，則任何更小的 $k' < k$ 也必然可行——只需捨棄多餘的配對，因此可行性具有單調性，故每個查詢可以對 $k$ 進行二分搜尋，找出最大的可行值。

檢查給定的 $k$ 是否可行

要檢查 $k$ 是否可行，最寬容的貪心策略是讓 1 盡量靠左、2 盡量靠右，以最大化中間能放 / 的範圍：

在查詢區間內，取左側第 $k$ 個 1 的位置。
在查詢區間內，取右側倒數第 $k$ 個 2 的位置。

若這兩個位置之間至少存在一個 /，則 $k$ 可行——選這兩個位置之間的任一個 / 即可配對。

反之，若這樣最寬容的安排都找不到中間的 /，任何其他選法只會讓 / 的可用範圍更窄，因此 $k$ 必然不可行。

找到區間內左側第 $k$ 個 1 和右側倒數第 $k$ 個 2 的位置，可以用二分搜尋在預先記錄的 1 和 2 的位置列表中找到。檢查兩個位置之間是否有 /，則可以用前綴和在 $\mathcal{O}(1)$ 時間內完成。

結論

固定 $k$ 時只需要關心「第 $k$ 個可用的 1」與「倒數第 $k$ 個可用的 2」之間是否有 /，因此每次可行性檢查只需兩次位置二分搜尋搭配一次前綴和查詢，可在 $\mathcal{O}(\log N)$ 內完成。

複雜度分析

時間複雜度： $\mathcal{O}(N + Q \log^2 N)$ $O (N + Q lo g^{2} N)$
- 預處理 $N$ 個字元的位置信息和前綴和需要 $\mathcal{O}(N)$ 。
- 對於每個查詢，二分答案 $k$ 需要 $\mathcal{O}(\log N)$ ，每次檢查 $k$ 的可行性又需要兩次二分搜尋（各 $\mathcal{O}(\log N)$ ）和一次前綴和查詢（ $\mathcal{O}(1)$ ），總計 $\mathcal{O}(\log^2 N)$ 。
空間複雜度： $\mathcal{O}(N)$

Code

from bisect import bisect_left, bisect_right
from collections import defaultdict
from itertools import accumulate


def solve():
    n, q = map(int, input().split())
    s = input()
    assert len(s) == n

    # 記錄每個字元出現的所有位置 (1-indexed)
    pos = defaultdict(list)
    for i, ch in enumerate(s, start=1):
        pos[ch].append(i)

    # '/' 的前綴和：ss[i] = s[1..i] 中 '/' 的個數
    ss = list(accumulate(map(lambda ch: ch == "/", s), initial=0))

    for _ in range(q):
        l, r = map(int, input().split())

        # 區間內沒有 '/' 則不可能形成 11/22
        if ss[r] - ss[l - 1] == 0:
            print(0)
            continue

        def check(mid: int) -> bool:
            # 在 [l, r] 內找第 mid 個 '1' 的位置
            idx1 = bisect_left(pos["1"], l) + mid - 1
            # 在 [l, r] 內找倒數第 mid 個 '2' 的位置
            idx2 = bisect_right(pos["2"], r) - mid
            if idx1 >= len(pos["1"]) or idx2 < 0:
                return False
            ll, rr = pos["1"][idx1], pos["2"][idx2]
            # [ll, rr] 之間是否有至少一個 '/'
            return ss[rr] - ss[ll - 1] > 0

        # 二分搜尋最大的可行 k
        left, right = 1, r - l + 1
        while left <= right:
            mid = (left + right) >> 1
            if check(mid):
                left = mid + 1
            else:
                right = mid - 1
        # 答案 = 2k + 1
        print(1 + (right << 1))


if __name__ == "__main__":
    solve()