#P9762. Triplet

    ID: 6387 传统题 3000ms 512MiB 尝试: 2 已通过: 2 难度: 8 上传者: 标签>CF2500提高+/省选-根号分块添加/删除事件扫描中维护贡献一维差分一维前缀和交换求和顺序计数

Triplet

题目描述

给定 nn 个闭区间 [li,ri][l_i,r_i]。求有多少个有序三元组 (i,j,k)(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,ki,j,k 均在 11 到 nn 之间,可以相等。

输入格式

第一行一个整数 nn。接下来 nn 行,第 ii 行两个整数 li,ril_i,r_i。

输出格式

输出一行一个整数,表示满足条件的三元组数。

样例

3
1 2
2 3
1 3
12

这 12 个三元组为 (1,1,1)(1,1,1)、(1,2,3)(1,2,3)、(2,2,2)(2,2,2)、(2,2,3)(2,2,3)、(2,3,1)(2,3,1)、(2,3,2)(2,3,2)、(2,3,3)(2,3,3)、(3,1,2)(3,1,2)、(3,2,2)(3,2,2)、(3,2,3)(3,2,3)、(3,3,2)(3,3,2)、(3,3,3)(3,3,3)。

大样例见原题下发文件。

数据范围

对于全部数据,1≤li≤ri≤n≤1051\le l_i\le r_i\le n\le10^5。

原题子任务 额外限制 分值
1 n≤500n\le500 10
2 n≤104n\le10^4 30
3 对所有 ii,li=1l_i=1
4 无

原题题面图片