LG#P1496. 火烧赤壁

火烧赤壁

P1496 火烧赤壁

题目描述

\hspace{15pt}曹操平定北方以后,于公元 208208 年率领大军南下,进攻刘表。曹军还没有到达荆州,刘表就已经病死,他的儿子刘琮听到曹军声势浩大,吓破了胆,先派人求降了。

\hspace{15pt}孙权任命周瑜为都督,拨给他三万水军,叫他同刘备协力抵抗曹操。

\hspace{15pt}隆冬的十一月,天气突然回暖,刮起了东南风。东吴船队离开北岸大约二里距离时,前面十条大船突然同时起火。火借风势,风助火威,十条火船好比十条火龙,闯进曹军水寨。那里的船舰都挤在一起,又躲不开,很快地都烧了起来,一眨眼工夫已经烧成一片火海。

\hspace{15pt}曹操气急败坏地把你找来,要你钻入火海,把连环线上着火船只被火烧到的总长度统计出来。

\hspace{15pt}具体来说,给定 nn 个着火区间,第 ii 个区间为 [ai,bi)\left[a_i, b_i\right),表示从坐标 aia_i 一直烧到坐标 bib_i,但不包含坐标 bib_i 本身。区间之间可以相交、嵌套或完全重合,同一点被多个区间覆盖时只计算一次。请求出这些区间并集的总长度。

输入格式

\hspace{15pt}第一行输入一个整数 n(1≦n≦2×104)n \left(1 \leqq n \leqq 2 \times 10^4\right) 代表起火的信息条数。

\hspace{15pt}此后 nn 行,第 ii 行输入两个整数 $a_i, b_i \left(-2^{31} \leqq a_i < b_i < 2^{31}\right)$ 代表第 ii 个着火区间的起点和终点,该区间为左闭右开区间 [ai,bi)\left[a_i, b_i\right)。

\hspace{15pt}保证所有着火区间并集的总长度小于 2312^{31}。

输出格式

\hspace{15pt}在一行上输出一个整数,代表燃烧位置的总长度。

测试样例

3
-1 1
5 11
2 9
11

样例 1 解释

\hspace{15pt}三个着火区间分别为 [−1,1)\left[-1, 1\right)、[5,11)\left[5, 11\right) 和 [2,9)\left[2, 9\right)。

∙ \hspace{23pt}\bullet\,[5,11)\left[5, 11\right) 与 [2,9)\left[2, 9\right) 有重叠,合并后得到 [2,11)\left[2, 11\right),长度为 11−2=911 - 2 = 9;

∙ \hspace{23pt}\bullet\,[−1,1)\left[-1, 1\right) 与上述区间不相交,长度为 1−(−1)=21 - (-1) = 2。

\hspace{15pt}因此并集的总长度为 9+2=119 + 2 = 11。

6
-5 -2
-3 1
0 4
3 8
10 12
11 15
18

样例 2 解释

\hspace{15pt}前四个区间 [−5,−2)\left[-5, -2\right)、[−3,1)\left[-3, 1\right)、[0,4)\left[0, 4\right)、[3,8)\left[3, 8\right) 依次首尾相接或重叠,合并后得到 [−5,8)\left[-5, 8\right),长度为 8−(−5)=138 - (-5) = 13。

\hspace{15pt}后两个区间 [10,12)\left[10, 12\right) 与 [11,15)\left[11, 15\right) 重叠,合并后得到 [10,15)\left[10, 15\right),长度为 15−10=515 - 10 = 5。

\hspace{15pt}因此并集的总长度为 13+5=1813 + 5 = 18。