区间相交

题目描述

给定编号为 $1$ 到 $N$ 的 $N$ 个区间，其定义如下：

• 若 $t_i=1$，区间 $i$ 为 $[l_i,r_i]$；
• 若 $t_i=2$，区间 $i$ 为 $[l_i,r_i)$；
• 若 $t_i=3$，区间 $i$ 为 $(l_i,r_i]$；
• 若 $t_i=4$，区间 $i$ 为 $(l_i,r_i)$。

求满足 $1 \le i \lt j \le N$ 且区间 $i$ 与区间 $j$ 相交的整数对 $(i,j)$ 的个数。

$[X,Y]$、$[X,Y)$、$(X,Y]$、$(X,Y)$ 分别是什么？

• 闭区间 $[X,Y]$ 是满足 $X \le x \le Y$ 的所有实数 $x$ 构成的区间。
• 半开区间 $[X,Y)$ 是满足 $X \le x \lt Y$ 的所有实数 $x$ 构成的区间。
• 半开区间 $(X,Y]$ 是满足 $X \lt x \le Y$ 的所有实数 $x$ 构成的区间。
• 开区间 $(X,Y)$ 是满足 $X \lt x \lt Y$ 的所有实数 $x$ 构成的区间。

粗略地说，方括号 $[]$ 表示包含端点，圆括号 $()$ 表示不包含端点。

输入格式

输入按以下格式从标准输入给出：

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

输出格式

输出区间 $i$ 与区间 $j$ 相交的整数对 $(i,j)$ 的个数。

样例

3
1 1 2
2 2 3
3 2 4

2

按题目定义，区间 $1$ 为 $[1,2]$，区间 $2$ 为 $[2,3)$，区间 $3$ 为 $(2,4]$。

满足区间相交的整数对 $(i,j)$ 有两对，即 $(1,2)$ 和 $(2,3)$。第一对的交集为 $[2,2]$，第二对的交集为 $(2,3)$。

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

102

数据范围

• $2 \le N \le 2000$
• $1 \le t_i \le 4$
• $1 \le l_i \lt r_i \le 10^9$
• 输入均为整数