分数: 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