← 返回题目列表

AtCoder · tkppc6_2_m

M. 分离

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

配点 : 800(+1) 点

故事

20XX 年,帕研放弃了技术室的深处,成为海盗,划向大海……

問題文

1 减去 N 由 N 人的海盗,1 减去 10^{12} 由 10^{12} 个宝物将被平分。每个海盗对于分配到的宝物有自己的偏好,海盗 i 是号码 在 L_i 以上 R_i 只想要符合以下条件的宝物,其他宝物不接受。在这里,在海盗之间有一个不成文的约定:“编号较大的海盗应当获得编号较小的海盗剩下的分赃”,因此所有 i,j\ (1 \leq i \lt j \leq N) 关于 L_j \leq L_i 和 R_i \leq R_j 都将得到满足。

这些天,海盗们一直在思考各种分赃方式。因此,在以下 Q 查询。

  • 海賊 l,l+1,\ldots,r 中平分宝物时,每个人能得到宝物数量的最小值最大能是多少。

制約

  • 2 \leq N \leq 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq L_i \leq R_i \leq 10^{12}\ (1 \leq i \leq N)
  • 全部 i,j\ (1 \leq i \lt j \leq N) , 当我输入L_j \leq L_i 和 R_i \leq R_j 满意 如果正确答案是满足
  • 在每个查询中, 左上角带有1 \leq l \leq r \leq N 满意 如果正确答案是满足
  • 所有输入均为整数

额外案例

满足以下约束条件的数据集(满足上述约束的 800 分的测试用例中正确的话,将额外获得 1 分。不过,在该数据集下,不保证低速语言可以 AC。 由

  • 2 \leq N \leq 5 \times 10^5
  • 1 \leq Q \leq 5 \times 10^5

入力

输入是按以下格式从标准输入给出的。

N
L_1 R_1
L_2 R_2
\hspace{0.5cm}\vdots
L_N R_N
Q
\text{query}_1
\text{query}_2
\hspace{0.4cm}\vdots
\text{query}_Q

i 查询内容为 它由 \text{query}_i 表示,其内容以以下格式给出。 请输出第

l r

出力

Q 跨线输出。 输出i\ (1 \leq i \leq Q) 在线 i 个查询的答案。 在第


入力例 1

2
2 4
1 5
2
1 2
2 2

出力例 1

2
5

1 个查询中,例如可以考虑以下的分配方式。

  • 海賊 1 的宝物 2,3 ,交给海盗 2 的宝物 4,5 。 对于第

2 个查询,只需分配所有的海盗 2 的宝物 1,2,3,4,5 。 记作


入力例 2

10
545730128881 685343573126
495640031759 777974687460
441446188770 793309056685
376909511228 836745593749
371724504348 838698721858
232388555737 839645478663
171431376831 859733468976
64650919635 891249391583
54537347654 900209259449
7975806821 908972571709
10
9 9
2 3
1 6
3 9
2 10
1 2
3 4
5 6
2 9
7 8

出力例 2

845671911796
175931433958
93394843502
120810273113
100110751654
139613444246
229918041261
303628461463
105708988974
413299235974

原案: 企鹅人