← 返回题目列表

AtCoder · abc365_g

G. AtCoder 办公室

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

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