C - 许多线段

得分：$300$分

题目描述

给定$N$个以$1$到$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 \leq i \lt j \leq N$的整数$(i,j)$使得区间$i$和区间$j$相交？

约束

• $2 \leq N \leq 2000$
• $1 \leq t_i \leq 4$
• $1 \leq l_i \lt r_i \leq 10^9$
• 输入中的所有值为整数。

输入

从标准输入得到以下格式的输入：

$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)$的数量。

3
1 1 2
2 2 3
3 2 4

2

如题目描述所定义的，区间$1$为$[1,2]$，区间$2$为$[2,3)$，区间$3$为$(2,4]$。

有两对满足区间$i$和区间$j$相交的整数$(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