分数: 500 点
问题陈述
一套 S 成对的非负整数和一个非负整数 x,让 f_S(x) 定义为 \displaystyle f_S(x)=\min_{(a, b) \in S} \left| \left| x-a \right| - b \right|.
我们有一套 T 非负整数对。最初, T=\lbrace (A, B)\rbrace.
流程 Q 查询。的 i-th 查询给出三个非负整数 t_i, a_i,和 b_i,并要求您执行以下操作。
- If t_i=1,添加到 T 一对 (a_i, b_i) 非负整数。
- If t_i=2,打印最小值 f_{T}(x) 为非负整数 x 这样 a_i \leq x \leq b_i.
约束
- 1 \leq Q \leq 2 \times 10^5
- 0 \leq A,B \leq 10^{9}
- t_i is 1 or 2.
- 0 \leq a_i,b_i \leq 10^{9}
- If t_i=2,那么 a_i \leq b_i.
- 至少有一个查询 t_i=2.
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
Q A B t_1 a_1 b_1 t_2 a_2 b_2 \vdots t_Q a_Q b_Q
输出
对于每个查询 t_i=2 按照给定的顺序,在其自己的行中打印答案。
示例输入 1
4 0 5 1 3 11 2 7 8 1 8 2 2 8 9
示例输出 1
2 1
在第二个查询中, T=\lbrace(0, 5), (3, 11) \rbrace。对于 x=7,我们有 f_T(7)=\min \lbrace \left| \left|7-0\right|-5\right|, \left| \left|7-3\right|-11\right| \rbrace=\min \lbrace 2, 7 \rbrace=2。同样, f_T(8)=3。因此,答案是 \min \lbrace 2, 3 \rbrace =2.
在第四个查询中, T=\lbrace(0, 5), (3, 11), (8, 2) \rbrace。在 8 \leq x \leq 9, f_T(x) 取最小值 f_T(9)=1 at x=9.
示例输入 2
2 1 2 1 2 3 2 2 6
示例输出 2
0
示例输入 3
20 795629912 123625148 2 860243184 892786970 2 645778367 668513124 1 531411849 174630323 1 635062977 195695960 2 382061637 411843651 1 585964296 589553566 1 310118888 68936560 1 525351160 858166280 2 395304415 429823333 2 583145399 703645715 2 97768492 218377432 1 707220749 459967102 1 210842017 363390878 2 489541834 553583525 2 731279777 811513313 1 549864943 493384741 1 815378318 826084592 2 369622093 374205455 1 78240781 821999998 2 241667193 243982581
示例输出 3
26468090 3491640 25280111 9543684 0 22804896 20649370 19245624 4849993 484865