AtCoder 🟢 ABC457E Crossing Table Cloth

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

🔗 ABC457E Crossing Table Cloth

Problem Statement

題目簡述

有 $N$ 個格子水平排成一列，從左到右編號為 $1,2,\ldots,N$。
有 $M$ 塊桌布，第 $i$ 塊桌布鋪上後會覆蓋格子 $L_i$ 到 $R_i$。
對每個詢問 $(S_q,T_q)$，判斷是否能從 $M$ 塊桌布中恰好選出兩塊並鋪上，使得格子 $S_q$ 到 $T_q$ 都被至少一塊桌布覆蓋，且除此之外沒有其他格子被覆蓋。

Constraints

約束條件

• $1 \leq N \leq 2 \times 10^5$
• $2 \leq M \leq 2 \times 10^5$
• $1 \leq L_i \leq R_i \leq N$
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq S_q \leq T_q \leq N$
• 所有輸入皆為整數

---

思路：端點分組 + 後綴最小值預處理

從條件拆解

題目要求恰好選兩塊桌布覆蓋指定的連續區間，且不能蓋到區間以外的格子，這包含了三個條件：

1. 必須有一塊桌布恰好從詢問左端點 $S$ 出發——若起點更左，會蓋到區間外的格子。
2. 必須有一塊桌布恰好到詢問右端點 $T$ 結束——若終點更右，同樣會超出。
3. 兩塊桌布的覆蓋區域必須銜接（可重疊，但不能有空隙）。

因此，每筆詢問的答案取決於：是否存在左端恰為 $S$ 的桌布，以及右端恰為 $T$ 的桌布，且兩者的覆蓋範圍能串成一段。

對於左端同為 $S$ 的所有桌布，右端越遠、涵蓋越廣，越容易和右側的桌布接上。對右端同為 $T$ 的桌布同理，左端越靠左、越容易和左側的桌布接上。因此我們可以在範圍內找出「最佳候選」：左端為 $S$ 的桌布中右端最遠的，以及右端為 $T$ 的桌布中左端最靠近的。

為什麼只需檢查最佳候選？

若存在某對桌布能成功覆蓋，那把左側那塊換成同左端中右端最遠的、右側那塊換成同右端中左端最靠左的，只會讓銜接條件更加寬鬆。
結論：每筆詢問只需檢查各端點上的「最佳候選」即可，不必枚舉所有組合。

情況一：存在恰好覆蓋 $[S, T]$ 的桌布

若存在恰好覆蓋 $[S,T]$ 的桌布，從左端 $S$ 和右端 $T$ 各自選出的最佳候選會指向同一塊桌布，違反必須選取兩塊不同桌布的限制。

此時需另找一塊桌布搭配，而能被選為第二塊的桌布，其覆蓋範圍必須完全落在 $[S,T]$ 內（否則會超出詢問區間）。所有落在 $[S,T]$ 內的桌布可歸為以下三種情形：

1. 完全與 $[S,T]$ 重疊：存在兩塊以上完全相同的 $[S,T]$ 桌布，直接取兩塊即可。
2. 左端比 $S$ 靠右，且右端不超過 $T$：存在一塊桌布滿足左端 $\ge S+1$、右端 $\le T$。
3. 右端比 $T$ 靠左，且左端不低於 $S$：存在一塊桌布滿足左端 $\ge S$、右端 $\le T-1$（即右端 $< T$）。

為何三類就能涵蓋所有可能？

$[S,T]$ 的任意真子區間，要麼左端嚴格在 $S$ 右邊、要麼右端嚴格在 $T$ 左邊（兩者可能同時成立），因此情形 2 和 3 合起來便涵蓋了所有不與 $[S,T]$ 完全相同的子區間。

後綴最小值預處理

情形 1 可直接由計數器判斷。情形 2 和 3 則需要回答一類共同問題：「是否存在某塊桌布，左端不小於 $x$、且右端不大於 $y$？」。

為此預處理一個後綴最小值陣列：對每個位置 $x$，記錄「所有左端 $\ge x$ 的桌布中，右端的最小值」。這樣一來，對任意查詢只需 $O(1)$ 時間——直接在該位置上讀取後綴最小值，並與 $y$ 比較即可。

對應到程式邏輯：

• 情形 2：查位置 $S+1$ 的後綴最小值是否 $\le T$
• 情形 3：查位置 $S$ 的後綴最小值是否 $< T$

情況二：根據端點分組，二分找最佳候選

若不存在恰好覆蓋 $[S,T]$ 的桌布，就必須從左端為 $S$ 的群組中選一塊、從右端為 $T$ 的群組中選另一塊，並確認兩塊的覆蓋範圍能無縫銜接。

前面的交換論證已經指出：對每個端點群組，只需考慮該組內的「最佳候選」——左端 $S$ 的群組中右端最遠的那塊、右端 $T$ 的群組中左端最靠左的那塊。因此每筆詢問的要務就是快速定位出這兩個候選。

分組與排序：

• 將桌布按左端點分組，每組內依右端點遞增排序。
• 將桌布按右端點分組，每組內依左端點遞增排序。

對詢問 $(S, T)$ 的查詢：

• 在左端為 $S$ 的群組中，二分找出右端不超過 $T$ 的最大值——即最後一個 $\le T$ 的元素。這保證選出的桌布不會超出詢問區間的右界。
• 在右端為 $T$ 的群組中，二分找出左端不小於 $S$ 的最小值——即第一個 $\ge S$ 的元素。這保證選出的桌布不會超出詢問區間的左界。

邊界處理

若任一群組中找不到符合條件的桌布——意味著該端點根本沒有可用的桌布，或所有符合端點條件的桌布覆蓋範圍都超出詢問區間——則直接判定為不可能。

銜接檢查：找到兩塊候選後，比較左側候選的右端 $+1$ 與右側候選的左端。若前者不小於後者，表示兩段覆蓋之間不存在未被覆蓋的空隙（可能重疊或恰好相鄰）；否則兩段之間有遺漏的格子，判定為失敗。

以 $+1$ 作為比較基準

設左側桌布覆蓋 $[S, r]$、右側桌布覆蓋 $[l, T]$。若 $l \le r+1$，則 $r$ 和 $l$ 之間不存在未被覆蓋的格子（重疊時 $l \le r$，相鄰時 $l = r+1$）。若 $l > r+1$，則 $[r+1,\, l-1]$ 的格子沒有任何桌布覆蓋。

複雜度分析

• 時間複雜度：$\mathcal{O}((M+Q)\log M + N)$
• 空間複雜度：$\mathcal{O}(M+N)$

---

Code

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


def solve():
    n, m = map(int, input().split())
    intervals = [tuple(map(int, input().split())) for _ in range(m)]

    cnt = defaultdict(int)
    byL = defaultdict(list)  # L -> List[(R, idx)]
    byR = defaultdict(list)  # R -> List[(L, idx)]
    minR_at_L = [float("inf")] * (n + 1)

    for i, (l, r) in enumerate(intervals):
        cnt[(l, r)] += 1
        byL[l].append(r)
        byR[r].append(l)
        minR_at_L[l] = min(minR_at_L[l], r)

    for l, arr in byL.items():
        arr.sort()
    for r, arr in byR.items():
        arr.sort()

    # suf[x] = 所有 L >= x 的桌布中，最小的 R
    suf = list(accumulate(minR_at_L[::-1], min, initial=float("inf")))[::-1]

    q = int(input())
    for _ in range(q):
        s, t = map(int, input().split())
        if s not in byL or t not in byR:
            print("No")
            continue

        if cnt[(s, t)] > 0:
            ok = False
            ok |= cnt[(s, t)] >= 2  # 有兩塊以上完全相同的 [s, t]
            ok |= suf[s + 1] <= t  # 存在 L > s 且 R <= t 的桌布
            ok |= suf[s] < t  # 存在 L >= s 且 R < t 的桌布
            print("Yes" if ok else "No")
            continue

        idx1 = bisect_right(byL[s], t) - 1
        idx2 = bisect_left(byR[t], s)

        if idx1 < 0 or idx2 == len(byR[t]):
            print("No")
            continue

        r = byL[s][idx1]
        l = byR[t][idx2]

        if l > r + 1:
            print("No")
        else:
            print("Yes")


if __name__ == "__main__":
    solve()