城市天际线(City Horizon)

题目描述

Farmer John 正带着他的奶牛去城市旅行！当太阳落下时，奶牛们凝望着城市的天际线，观察着由矩形建筑形成的美丽轮廓。

整个地平线可以用一个包含 $N$ 座建筑物（$1\le N \le4\times10^4$）的坐标轴表示。第 $i$ 座矩形建筑的底部轮廓从 $A_i$ 点延伸到 $B_i$ 点（$1\le A_i<B_i\le10^9$），高度为 $H_i$（$1\le H_i\le10^9$）。请计算出所有 $N$ 座建筑物叠加起来形成的轮廓总面积（以平方单位计）。

输入格式

第一行：一个整数 $N$。

第二行至第 $N + 1$ 行：每行输入三个用空格分开的整数 $A_i$、$B_i$、$H_i$，表示一个矩形建筑。

输出格式

一行：表示所有 $N$ 座建筑物叠加起来形成的轮廓总面积。

样例输入 #1

4
2 5 1
9 10 4
6 8 2
4 6 3

样例输出 #1

16

数据范围

对于 $100\%$ 的数据，$1 \le N \le 4 \times 10^4$，$1 \le A_i < B_i \le 10^9$，$1 \le H_i \le 10^9$。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1750。

测试点分布

出处：原题链接