配点 : 500 点
問題文
N 有真竹子, 它们的编号最大为1 减去 N 。 时间 在 0 中,所有竹子的高度为 0 。 每根竹子都有一个时间 1 高度随着时间的推移而增加。 1 将会增加。
Nao砍竹子的活动 M 已安排。 i 第一个事件是时间 T_i 在这种情况下,号码 L_i 以上 R_i 砍掉下面所有的竹子。 奈绪很高 当砍 x 竹子时,她 获得 x 点。 另外,砍伐竹子的高度为 0 然而,在此之后竹子将继续生长。
M 求 Nao 在该赛事中获得的总分。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- 1 \leq T_1 < T_2 < \cdots < T_M \leq 10^9
- 1 \leq L_i \leq R_i \leq N
- 所有输入值都是整数。 如果您想走
入力
输入是按以下格式从标准输入给出的。
N M T_1 L_1 R_1 T_2 L_2 R_2 \vdots T_M L_M R_M
出力
M 输出 Nao 在该事件中获得的总分。 第
入力例 1
4 2 2 1 2 5 2 3
出力例 1
12
1 个事件发生的时间 2 每根竹子的高度是 2,2,2,2 。 竹子 当 1 和 按字典顺序比较 2 被砍伐时,每根竹子的高度为 0,0,2,2 。
2 个事件发生的时间 5 每根竹子的高度是 3,3,5,5 。 竹子 当 2 和 按字典顺序比较 3 被砍伐时,每根竹子的高度为 3,0,0,5 。
2 每次活动中砍伐的竹子高度为 2,2,3,5 因此,它是 12 就是答案。
入力例 2
10 5 8 1 4 11 6 7 20 1 1 31 9 9 36 1 1
出力例 2
113
入力例 3
10 10 76724435 3 4 118633459 1 2 288866156 6 9 470883673 6 10 521545097 2 4 827053186 1 1 856004743 2 4 873331881 1 1 909855542 6 10 916091889 8 9
出力例 3
8003096514