\(S_q,T_q\) を単に \(S,T\) と表記します。

\([S,T]\) の区間のみをちょうど覆う必要があるので、左端を \(S\) に持つ布、右端を \(T\) に持つ布がそれぞれ必要です。

[1] \([S,T]\) をちょうど覆う布が存在する場合

答えが Yes となる場合は以下の \(3\) パターンで網羅できます。

• \([S,T]\) をちょうど覆う布が \(2\) 枚以上ある
• \([S+1,T]\) の範囲内に収まる布が存在する
• \([S,T-1]\) の範囲内に収まる布が存在する

\(1\) パターン目は set などで布を管理することで求めることができます。

\(2\) パターン目は「布の左端が \(i\) 以上であるような布の右端の最小値」を管理した配列を事前に計算することで高速に判定することができます。\(3\) パターン目を同様です。

[2] \([S,T]\) をちょうど覆う布が存在しない場合

\(1\) 枚目の布で左端を \(S\) に持つ布を、\(2\) 枚目の布で右端を \(T\) に持つ布を選ぶ必要があります。

また、\(1\) 枚目の布は左端を \(S\) に持つ布の中で右端が \(T\) 以下で最大の布を選ぶとして良いです。\(2\) 枚目の布も同様に右端を \(T\) に持つ布の中で左端が \(S\) 以上で最小の布を選ぶとして良いです。

これらは事前に各マスを右端・左端とする布に対するもう一端を配列として持っておき、そこに対する二分探索を行うことで高速に求めることができます。

そのようにして選んだ \(2\) 枚の布が条件を満たすか判定すれば良いです。

以上を適切に実装することでこの問題に正答することができます。計算量は \(O(N+(M+Q)\log M)\) です。

実装例(Python3)

import sys
from bisect import bisect_right, bisect_left
from collections import defaultdict

input = sys.stdin.readline

N, M = map(int, input().split())

by_l = [[] for _ in range(N + 1)]
by_r = [[] for _ in range(N + 1)]
cnt = defaultdict(int)
INF = 10**9
min_r_at_l = [INF] * (N + 2)
for _ in range(M):
    L, R = map(int, input().split())
    by_l[L].append(R)
    by_r[R].append(L)
    cnt[(L, R)] += 1
    if R < min_r_at_l[L]:
        min_r_at_l[L] = R

for i in range(1, N + 1):
    by_l[i].sort()
    by_r[i].sort()

suf_min_r = [INF] * (N + 3)
for i in range(N, 0, -1):
    suf_min_r[i] = min(suf_min_r[i + 1], min_r_at_l[i])

Q = int(input())
ans = []

for _ in range(Q):
    S, T = map(int, input().split())

    if cnt[(S, T)] > 0:
        ok = False
        ok |= cnt[(S, T)] >= 2
        ok |= suf_min_r[S + 1] <= T
        ok |= suf_min_r[S] <= T - 1
        print("Yes" if ok else "No")
        continue

    ok = False

    rs = by_l[S]
    pos_r = bisect_right(rs, T) - 1

    ls = by_r[T]
    pos_l = bisect_left(ls, S)

    if pos_r >= 0 and pos_l < len(ls):
        r1 = rs[pos_r]
        l2 = ls[pos_l]
        ok |= l2 <= r1 + 1
    print("Yes" if ok else "No")