题目描述

$1$ から $N$ までの番号が付いた $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\ \lt\ 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$ $\hspace{1cm}\vdots$ $t_N$ $l_N$ $r_N$

输出格式

区間 $i$ と区間 $j$ が共通部分を持つような整数の組 $(i,j)$ の個数を出力せよ。

题目大意

题目翻译

给定 $N$ 个区间，其中第 $i$ 个区间由一个标识符 $t_i$ 及两个端点 $l_i,r_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)$

其中闭区间指包含端点的区间，用方括号表示。开区间指不包含端点的区间，用圆括号表示。半开半闭区间同理。

现在，请你求出这 $N$ 个区间中相交区间的对数。

样例解释

对于输入样例 $1$，题目中给定的区间为 $[1,2]$，$[2,3)$，和 $(2,4]$。第一个区间和第二个区间相交（均包含整数 $2$），第二个区间和第三个区间相交（均包含任意 $2 < x < 3$ 的实数 $x$）。因此有两对相交区间，答案为 $2$。

3
1 1 2
2 2 3
3 2 4

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

102

提示

制約

• $2\ \leq\ N\ \leq\ 2000$
• $1\ \leq\ t_i\ \leq\ 4$
• $1\ \leq\ l_i\ \lt\ r_i\ \leq\ 10^9$
• 入力は全て整数

Sample Explanation 1

問題文中の定義より、区間 $1$ は $[1,2]$, 区間 $2$ は $[2,3)$, 区間 $3$ は $(2,4]$ です。 区間 $i$ と区間 $j$ が共通部分を持つような整数の組 $(i,j)$ は、$(1,2)$ と $(2,3)$ の $2$ つとなります。それぞれ、$[2,2]$ と $(2,3)$ を共通部分として持っています。