航班预订统计

题目描述

这里有 $n$ 个航班，它们分别从 $1$ 到 $n$ 进行编号。

有一份航班预订表 $bookings$，表中第 $i$ 条预订记录$bookings[i] = [firsti, lasti, seatsi]$ 意味着在从 $firsti$到 $lasti$（包含 $firsti$ 和 $lasti$）的 每个航班 上预订了 $seatsi$个座位。

请你返回一个长度为 $n$ 的数组 $answer$，里面的元素是每个航班预定的座位总数。

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示航班数量和预订记录条数。

接下来 $m$ 行，每行包含三个整数 $firsti$、$lasti$ 和 &seatsi&，表示一条预订记录。

输出格式

输出一行，包含 $n$个整数，用空格分隔，表示每个航班预定的座位总数。

提示

$1 <= n <= 2 * 10^4$

$1 <= m <= 2 * 10^4$

$1 <= firsti <= lasti <= n$

$1 <= seatsi <= 10^4$

输入输出样例

5 3
1 2 10
2 3 20
2 5 25

10 55 45 25 25

2 2
1 2 10
2 2 15

10 25

解题思路：使用差分数组（Difference Array）优化区间加法操作，时间复杂度 O(n + m)，空间复杂度 O(n)。