P - Connect the Dots Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 4 点

問題文

円周上に 2N 個の頂点が、時計回りに頂点 1, 頂点 2, \ldots, 頂点 2N の順に並んでいます。

長さ N の整数対の列 ((A_1,B_1),(A_2,B_2),\ldots,(A_N,B_N)) が与えられます。2N 個の値 A_1,\ldots,A_N,B_1,\ldots,B_N はすべて異なります。

クエリを Q 個処理してください。j 番目のクエリでは整数 l_j,r_j が与えられます。このクエリに対して、以下の条件をすべて満たすように曲線を引けるか判定してください。

  • i=l_j,l_j+1,\ldots,r_j のそれぞれについて、頂点 A_i と頂点 B_i を結ぶ曲線を 1 本引く。
  • すべての曲線は円の内部または円周上にある。
  • 異なる 2 本の曲線は交わらない。

各クエリは独立です。あるクエリで引いた曲線は他のクエリには影響しません。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq A_i \lt B_i \leq 2N
  • (A_1,\ldots,A_N,B_1,\ldots,B_N) は (1,2,\ldots,2N) の順列
  • 1 \leq l_j \leq r_j \leq N
  • 入力される数値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N Q
A_1 B_1
A_2 B_2
\vdots
A_N B_N
l_1 r_1
l_2 r_2
\vdots
l_Q r_Q

出力

Q 行出力せよ。

j 行目には、j 番目のクエリについて条件を満たすように曲線を引けるなら Yes を、引けないなら No を出力せよ。

入力例 1

5 6
1 10
2 5
3 4
6 8
7 9
1 3
2 4
4 5
1 5
3 3
3 4

出力例 1

Yes
Yes
No
No
Yes
Yes

1 番目のクエリでは、頂点 1 と 10、頂点 2 と 5、頂点 3 と 4 を結ぶ曲線を互いに交わらないように引けます。

3 番目のクエリでは、頂点 6 と 8 を結ぶ曲線と、頂点 7 と 9 を結ぶ曲線を交わらないように引くことはできません。

入力例 2

4 4
1 5
2 6
3 4
7 8
1 2
2 4
1 3
3 4

出力例 2

No
Yes
No
Yes

Score: 4 points

Problem Statement

There are 2N vertices on a circle, arranged clockwise in the order vertex 1, vertex 2, \ldots, vertex 2N.

You are given a sequence of N pairs of integers ((A_1,B_1),(A_2,B_2),\ldots,(A_N,B_N)). The 2N values A_1,\ldots,A_N,B_1,\ldots,B_N are all distinct.

Process Q queries. In the j-th query, you are given integers l_j,r_j. Determine whether curves can be drawn satisfying all of the following conditions:

  • For each i=l_j,l_j+1,\ldots,r_j, draw 1 curve connecting vertex A_i and vertex B_i.
  • Every curve lies inside the circle or on its circumference.
  • No 2 distinct curves intersect.

Each query is independent. Curves drawn in one query do not affect other queries.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq A_i \lt B_i \leq 2N
  • (A_1,\ldots,A_N,B_1,\ldots,B_N) is a permutation of (1,2,\ldots,2N).
  • 1 \leq l_j \leq r_j \leq N
  • All numerical values in the input are integers.

Input

The input is given from Standard Input in the following format:

N Q
A_1 B_1
A_2 B_2
\vdots
A_N B_N
l_1 r_1
l_2 r_2
\vdots
l_Q r_Q

Output

Print Q lines.

On the j-th line, print Yes if curves satisfying the conditions can be drawn for the j-th query, and No otherwise.

Sample Input 1

5 6
1 10
2 5
3 4
6 8
7 9
1 3
2 4
4 5
1 5
3 3
3 4

Sample Output 1

Yes
Yes
No
No
Yes
Yes

For query 1, curves connecting vertices 1 and 10, vertices 2 and 5, and vertices 3 and 4 can be drawn without intersecting each other.

For query 3, a curve connecting vertices 6 and 8 and a curve connecting vertices 7 and 9 cannot be drawn without intersecting each other.

Sample Input 2

4 4
1 5
2 6
3 4
7 8
1 2
2 4
1 3
3 4

Sample Output 2

No
Yes
No
Yes