AT_abc207_c.[ABC207C] Many Segments

普及-

通过率：0%

AC君温馨提醒

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

题目描述

给定 $N$ 个编号为 $1$ 到 $N$ 的区间。第 $i$ 个区间的定义如下：

如果 $t_i=1$ ，则区间为 $[l_i, r_i]$ ；
如果 $t_i=2$ ，则区间为 $[l_i, r_i)$ ；
如果 $t_i=3$ ，则区间为 $(l_i, r_i]$ ；
如果 $t_i=4$ ，则区间为 $(l_i, r_i)$ 。

请问满足 $1 \leq i < j \leq N$ 的整数对 $(i, j)$ 中，有多少对区间 $i$ 和区间 $j$ 存在公共部分？

区间 $[X,Y]$ 、 $[X,Y)$ 、 $(X,Y]$ 、 $(X,Y)$ 的定义如下：

闭区间 $[X,Y]$ 表示所有大于等于 $X$ 且小于等于 $Y$ 的实数的集合；
半开区间 $[X,Y)$ 表示所有大于等于 $X$ 且小于 $Y$ 的实数的集合；
半开区间 $(X,Y]$ 表示所有大于 $X$ 且小于等于 $Y$ 的实数的集合；
开区间 $(X,Y)$ 表示所有大于 $X$ 且小于 $Y$ 的实数的集合。

简而言之，方括号 $[]$ 表示包含端点，圆括号 $()$ 表示不包含端点。

输入格式

输入以如下格式从标准输入读入：

$N$
$t_1$ $l_1$ $r_1$
$t_2$ $l_2$ $r_2$
$\vdots$
$t_N$ $l_N$ $r_N$

输出格式

输出区间 $i$ 和区间 $j$ 存在公共部分的整数对 $(i, j)$ 的个数。

输入输出样例

输入#1
```
3
1 1 2
2 2 3
3 2 4
```
输出#1
```
2
```

输入#2

19
4 210068409 221208102
4 16698200 910945203
4 76268400 259148323
4 370943597 566244098
1 428897569 509621647
4 250946752 823720939
1 642505376 868415584
2 619091266 868230936
2 306543999 654038915
4 486033777 715789416
1 527225177 583184546
2 885292456 900938599
3 264004185 486613484
2 345310564 818091848
1 152544274 521564293
4 13819154 555218434
3 507364086 545932412
4 797872271 935850549
2 415488246 685203817

输出#2

说明/提示

限制条件

$2 \leq N \leq 2000$
$1 \leq t_i \leq 4$
$1 \leq l_i < r_i \leq 10^9$
输入均为整数

样例解释 1

根据题目中的定义，区间 $1$ 为 $[1,2]$ ，区间 $2$ 为 $[2,3)$ ，区间 $3$ 为 $(2,4]$ 。存在公共部分的整数对 $(i, j)$ 有 $(1,2)$ 和 $(2,3)$ 共 $2$ 对。它们分别有 $[2,2]$ 和 $(2,3)$ 作为公共部分。

由 ChatGPT 4.1 翻译

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

首页