配点 : 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
原案: 企鹅人