#P2687. 交与并

    ID: 1757 传统题 2000ms 512MiB 尝试: 798 已通过: 170 难度: 8 上传者: 标签>CF2500提高+/省选-自定义排序规则消除被支配候选普通线段树线段树上二分决策单调性分治算法决策单调性优化DP

交与并

题目描述

对于一个区间集合 {A1,A2,…,AK}\{A_1,A_2,\ldots,A_K\}(K>1K>1,Ai≠Aj (i≠j)A_i \neq A_j \, (i \neq j)),我们定义其权值为

$$W = |A_1 \cup A_2 \cup \ldots \cup A_K| \times |A_1 \cap A_2 \cap \ldots \cap A_K|$$

当然,如果这些区间没有交集,则权值为 00。

给定 NN 个各不相同的区间,请你从中找出若干个区间使其权值最大。

输入格式

第一行包含一个整数 N(1<N≤106)N(1<N \leq 10^6)。

接下来的 NN 行,每行包含两个整数 l,r(1≤l<r≤106)l, r(1 \leq l < r \leq 10^6),表示一个区间。

输出格式

输出最大权值。

输入样例

4
1 6
4 8
2 7
3 5

输出样例

24

提示

选择第 11 个和第 33 个区间,它们的交集为 (2,6)(2,6),并集为 (1,7)(1,7),权值为4×6=244 \times 6 = 24。