← 返回题目列表

AtCoder · abc405_f

I. 和弦交叉

中文机器翻译题面 查看原题

分数: 525 点

问题陈述

在一个圆圈上, 2N 点等间隔放置并编号 1,2,\dots,2N 从任意点开始按顺时针顺序。

有 M 线段编号 1,2,\dots,M 连接这些点。段 i 连接点 A_i 和 B_i。 在这里, A_i 和 B_i 是不同的 偶数。 保证这些线段中没有两个线段共享一个点。

流程 Q 查询。的 j第一个查询如下:

  • 你有两个不同的 奇数 C_j 和 D_j。其中 M 片段 1,2,\dots,M,找出有多少个与线段连接点共享一个点 C_j 和 D_j.

约束

  • 2 \le N \le 10^6
  • 1\leq M \leq \min\left(\lfloor\frac{N}{2}\rfloor, 2\times 10^5\right)
  • 1 \le Q \le 2 \times 10^5
  • 1 \le A_i < B_i \le 2N
  • 1 \le C_j < D_j \le 2N
  • A_i 和 B_i 是偶数。
  • C_j 和 D_j 是奇数。
  • 对于任何 i_1 和 i_2 (i_1 \neq i_2),段 i_1 和 i_2 不分享一点。
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M
Q
C_1 D_1
C_2 D_2
\vdots
C_Q D_Q

输出

输出 Q 行。 的 j第行 (1\leq j \leq Q) 应包含以下问题的答案 j第一个查询。


示例输入 1

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

示例输出 1

1
2
0

上图说明了示例输入 1。黑点是 2N\ (=8) 点,蓝色实线是初始的 M\ (=2) 段,红色虚线是 Q\ (=3) 查询段。

  • 对于第一个查询,线段连接点 1 和 3 与一个初始线段相交:线段 1.
  • 对于第二个查询,线段连接点 3 和 7 与两个初始线段相交:线段 1 和 2.
  • 对于第三次查询,线段连接点 1 和 5 与零个初始线段相交。

示例输入 2

20 7
24 34
26 28
18 38
2 14
8 12
30 32
20 22
10
7 29
31 39
9 21
19 29
15 21
11 39
17 21
15 31
5 25
25 31

示例输出 2

3
3
4
1
2
2
2
3
3
1