We simply write \(S_q\) and \(T_q\) as \(S\) and \(T\).

Since the two cloths must cover exactly \([S,T]\), we need at least one cloth with left end \(S\), and one cloth with right end \(T\).

[1] If there exists a cloth that covers exactly \([S,T]\)

A Yes case always falls into one of the following three:

• There exist two or more cloths that cover exactly \([S,T]\)
• There exists a cloth contained in \([S+1,T]\)
• there exists a cloth contained in \([S,T-1]\)

The first pattern can be counted by managing the cloths in a set.

The second pattern can be counted by precalculating an array containing “the minimum right end of a cloth with left end greater than or equal to \(i\).” Same goes for the third pattern.

[2] If there does not exist a cloth that covers exactly \([S,T]\)

Among the chosen cloths, one cloth must have \(S\) as the left end, and the other \(T\) as the right.

For the former, we may always pick the cloth, among those with \(S\) as the left end, with the largest right end less than or equal to \(T\). Likewise, as the latter we may always pick, among those with \(T\) as the right end, with the smallest left end greater than or equal to \(S\).

Both can be found by binary searching on a precalculated array containing, for each position of the left or right end, an array of the positions of the other ends.

Once we decide them, check if they actually satisfy the conditions, and we are done.

The problem can be solved by appropriately implementing the algorithm above. The time complexity is \(O(N+(M+Q)\log M)\).

Sample code (Python 3)

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")