分数: 575 点
问题陈述
N 人们在 AtCoder 办公室工作。
办公室保存出入境记录,并有过 M 自记录开始以来的进入和退出。
的 i-th (1\leq i\leq M) 记录由一对整数表示 (T_i, P_i),表明在时间 T_i, P_i- 第一个人要么进入办公室(如果在外面),要么离开办公室(如果在里面)。
据了解,记录开始时所有人都在办公室外面,现在他们也在外面。
答案 Q 按以下格式查询。
对于 i-th (1\leq i\leq Q) 查询,给你一对整数 (A_i, B_i)。求两个时间段的总长度 A_i-th 和 自记录开始以来,第 B_i人在办公室内。
约束
- 2\leq N\leq2\times10^5
- 2\leq M\leq2\times10^5
- 1\leq T_1\lt T_2\lt\dotsb\lt T_M\leq10^9
- 1\leq P_i\leq N\ (1\leq i\leq M)
- 对于每个 1\leq p\leq N,索引数量 i 这样 P_i=p 是偶数。
- 1\leq Q\leq2\times10^5
- 1\leq A_i\lt B_i\leq N\ (1\leq i\leq Q)
- 所有输入均为整数。
输入
输入由标准输入按以下格式给出:
N M T_1 P_1 T_2 P_2 \vdots T_M P_M Q A_1 B_1 A_2 B_2 \vdots A_Q B_Q
输出
打印 Q 行。 的 i第行 (1\leq i\leq Q) 应包含以下问题的答案 i第一个查询。
示例输入 1
3 8 10 1 20 2 30 1 40 3 60 3 70 1 80 2 90 1 3 1 2 1 3 2 3
示例输出 1
20 0 20
下图显示了三个人各自在办公室内度过的时间。

每个查询的答案如下:
- 第一个人和第二个人当时都在办公室内 20 到时间 30 和时间 70 到时间 80。这两个时期的长度都是 10,所以打印总数,即 20.
- 第一个人和第三个人从来没有同时进入办公室,所以打印 0.
- 第二个人和第三个人当时都在办公室内 40 到时间 60。这段时间的长度是 20,所以打印 20.
示例输入 2
10 20 10257 9 10490 4 19335 1 25893 5 32538 9 33433 3 38522 9 40629 9 42896 5 52106 1 53024 3 55610 5 56721 9 58286 9 63128 3 70513 3 70977 4 74936 5 79883 9 95116 9 7 1 3 3 9 1 9 4 9 1 5 5 9 3 5
示例输出 2
18673 2107 15310 25720 17003 10317 16848