← 返回题目列表

AtCoder · arc155_b

B. Abs 绝对功能

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

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