#CW15. 查询(query)

查询(query)

题目描述

有一条由连续排列的 nn 个格子组成的木板,格子从左到右编号为 11 到 nn。

Alice 和 Bob 分别站在一个格子上,并且始终满足 Alice 所在位置小于 Bob 所在位置(即在 Bob 左边)。

木板上有 mm 块跳板,第 ii 块跳板安装在位置 xix_i,使用后会落到位置 yiy_i。同一位置可以有多块跳板,跳板可以被不限次数地使用。

一次动作中,恰好一人进行以下操作之一:

  1. 行走:
    • Alice 向右移动一格;
    • Bob 向左移动一格。
  2. 跳跃:使用当前所在位置的一块跳板,从 xix_i 跳到 yiy_i。

每次动作后都必须满足 Alice 仍在 Bob 的左侧,否则该动作不能执行。

现在有 QQ 个查询。第 jj 个查询给出 aj,bj,cj,dja_j, b_j, c_j, d_j,其中 1≤aj<bj≤n1 \le a_j < b_j \le n,1≤cj<dj≤n1 \le c_j < d_j \le n。

判断是否可以通过若干次合法动作,使 Alice 和 Bob 从 (aj,bj)(a_j,b_j) 移动到 (cj,dj)(c_j,d_j)。

对每个查询输出其是否有效。

输入格式

第一行依次给出两个以空格分隔的整数 nn 和 mm。

接下来的 mm 行给出 mm 块跳板的信息。其中第 ii 行依次给出两个以空格分隔的整数 xix_i 和 yiy_i,表示第 ii 块跳板。

下一行给出查询数量 QQ。

接下来的 QQ 行给出 QQ 个查询的信息。其中第 jj 行依次给出四个整数 aj,bj,cj,dja_j, b_j, c_j, d_j。

输出格式

从第一行开始依次输出 QQ 行答案。

第 jj 行输出第 jj 个查询的答案:若可以将 Alice 和 Bob 从 (aj,bj)(a_j,b_j) 移动到 (cj,dj)(c_j,d_j),输出 YES;否则输出 NO。

样例 1 输入

6 2
3 5
4 2
4
2 4 3 4
2 3 2 5
2 3 4 5
3 4 1 2

样例 1 输出

YES
YES
YES
NO

样例 2 输入

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

样例 2 输出

YES
NO
YES
YES
NO

数据范围

对于所有测试数据,保证:

  • 2≤n≤2000002 \le n \le 200000;
  • 0≤m≤2000000 \le m \le 200000;
  • 1≤Q≤5000001 \le Q \le 500000;
  • 对于每个整数 ii,1≤xi,yi≤n1 \le x_i, y_i \le n 且 xi≠yix_i \ne y_i;
  • 对于每个整数 jj,1≤aj<bj≤n1 \le a_j < b_j \le n 且 1≤cj<dj≤n1 \le c_j < d_j \le n。
测试点 n,m≤n, m \le Q≤Q \le 特殊性质
1∼41 \sim 4 1010 55 无
5∼85 \sim 8 100100
9∼119 \sim 11 200000200000 500000500000 ∀i≤m\forall i \le m,xi<yix_i < y_i
12∼1312 \sim 13 30003000 无
14∼1514 \sim 15 200000200000 1010
16∼2016 \sim 20 500000500000