给定 n 个闭区间 [li,ri]。求有多少个有序三元组 (i,j,k) 满足
$$i\in[l_k,r_k],\qquad j\in[l_i,r_i],\qquad k\in[l_j,r_j].$$i,j,k 均在 1 到 n 之间,可以相等。
第一行一个整数 n。接下来 n 行,第 i 行两个整数 li,ri。
输出一行一个整数,表示满足条件的三元组数。
3
1 2
2 3
1 3
12
这 12 个三元组为 (1,1,1)、(1,2,3)、(2,2,2)、(2,2,3)、(2,3,1)、(2,3,2)、(2,3,3)、(3,1,2)、(3,2,2)、(3,2,3)、(3,3,2)、(3,3,3)。
大样例见原题下发文件。
对于全部数据,1≤li≤ri≤n≤105。
| 原题子任务 | 额外限制 | 分值 |
|---|---|---|
| 1 | n≤500 | 10 |
| 2 | n≤104 | 30 |
| 3 | 对所有 i,li=1 | |
| 4 | 无 |