AT_arc155_b.[ARC155B] Abs Abs Function

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个由两个非负整数组成的二元组集合 $S$ ，以及一个非负整数 $x$ ，定义 $f_S(x)$ 为

$f_S(x)=\min_{(a,\,b)\in S} \left|\,|x-a|-b\,\right|$

有一个由两个非负整数组成的二元组集合 $T$ 。初始时 $T=\lbrace (A,\,B)\rbrace$ 。

请处理 $Q$ 个查询。对于第 $i$ 个查询，给出三个非负整数 $t_i,\,a_i,\,b_i$ ，请按如下方式处理：

当 $t_i=1$ 时，向 $T$ 中添加二元组 $(a_i,\,b_i)$ 。
当 $t_i=2$ 时，输出满足 $a_i\leq x\leq b_i$ 的所有非负整数 $x$ 中 $f_T(x)$ 的最小值。

输入格式

输入按以下格式从标准输入读入。

$Q\ A\ B\ t_1\ a_1\ b_1\ t_2\ a_2\ b_2\ \cdots\ 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
```
输入#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

说明/提示

数据范围

$1\leq Q\leq 2\times 10^5$
$0\leq A,B\leq 10^9$
$t_i$ 为 $1$ 或 $2$
$0\leq a_i,b_i\leq 10^9$
当 $t_i=2$ 时， $a_i\leq b_i$
至少存在一个 $t_i=2$ 的查询
所有输入的值均为整数

样例解释 1

执行第 2 个查询时， $T=\lbrace(0,\,5),\ (3,\,11)\rbrace$ ，例如 $x=7$ 时， $f_T(7)=\min\lbrace\,|\ |7-0|-5|,\ |\ |7-3|-11|\,\rbrace=\min\lbrace 2,\,7\rbrace=2$ 。同理， $f_T(8)=3$ 。因此，第 2 个查询的答案为 $\min\lbrace 2,\,3\rbrace=2$ 。执行第 4 个查询时， $T=\lbrace(0,\,5),\ (3,\,11),\ (8,\,2)\rbrace$ ，在 $8\leq x\leq 9$ 时， $f_T(x)$ 在 $x=9$ 取得最小值 $f_T(9)=1$ 。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页