题目描述

小 A 在夜晚进行天文观测，他在一个 $N \times N$ 的网格天幕上标记了 $M$ 颗恒星。每颗恒星都有一个坐标 $(x_i, y_i)$ 和一个亮度值 $v_i$。

小 A 发现了一个有趣的现象：如果一颗恒星 A 位于另一颗恒星 B 的左上方（即 $x_A < x_B$ 且 $y_A < y_B$），那么从观测者的角度看，A 会部分遮挡 B 的光线，导致 B 的有效亮度降低。

定义一颗恒星 B 的有效亮度为：

$$\text{Eff}(B) = v_B - \sum_{A: x_A < x_B, y_A < y_B} v_A$$

注意，如果计算结果为负数，则保留负值（表示完全被遮挡且产生阴影）。

小 A 想知道所有恒星的有效亮度之和是多少。由于答案可能很大，请输出对 $10^9+7$ 取模后的结果。

输入格式

第一行包含两个整数 $N$ 和 $M$，分别表示网格大小和恒星数量。 接下来 $M$ 行，每行包含三个整数 $x_i, y_i, v_i$，表示第 $i$ 颗恒星的坐标和亮度。

输出格式

输出一行一个整数，表示所有恒星有效亮度之和模 $10^9+7$ 的结果。

样例

3 4
1 2 5
2 3 8
3 1 3
2 1 2

13

样例解释

恒星列表：

1. $(1,2), v=5$
2. $(2,3), v=8$
3. $(3,1), v=3$
4. $(2,1), v=2$

计算每颗恒星的有效亮度：

• 恒星 1 $(1,2)$: 没有 $x<1$ 且 $y<2$ 的恒星。$\text{Eff} = 5 - 0 = 5$。
• 恒星 2 $(2,3)$: 满足 $x<2, y<3$ 的是恒星 1 $(1,2)$。$\text{Eff} = 8 - 5 = 3$。
• 恒星 3 $(3,1)$: 没有 $y<1$ 的恒星（因为坐标从1开始，且最小y为1）。$\text{Eff} = 3 - 0 = 3$。
• 恒星 4 $(2,1)$: 没有 $x<2$ 且 $y<1$ 的恒星。$\text{Eff} = 2 - 0 = 2$。

总和 = $5 + 3 + 3 + 2 = 13$。 等等，让我重新检查样例数据与逻辑。 题目要求输出有效亮度之和。 让我们重新手动计算一下样例： 恒星1: (1,2), v=5. 左边上方无点。Sum_v_A = 0. Eff = 5. 恒星2: (2,3), v=8. 左边上方有(1,2)。Sum_v_A = 5. Eff = 8 - 5 = 3. 恒星3: (3,1), v=3. 左边上方无点(y必须<1，不可能)。Sum_v_A = 0. Eff = 3. 恒星4: (2,1), v=2. 左边上方无点(y必须<1，不可能)。Sum_v_A = 0. Eff = 2. 总和 = 5 + 3 + 3 + 2 = 13。

哎呀，样例输出写的是6？这说明我上面的样例数据或者计算有误，或者我对题意的理解需要调整以匹配常见的NOI风格题目。通常这类题目是求 $\sum v_B - \sum_{A<B} v_A$。 $\sum v_B = 5+8+3+2 = 18$. 遮挡总和 $S_{occl} = \sum_{B} \sum_{A: A<B} v_A$. 对于 B=2, A=1 contributes 5. 其他没有贡献。 $S_{occl} = 5$. Total Eff = $18 - 5 = 13$.

如果样例输出是6，那么我的样例数据构造有问题，或者题目定义不同。 让我们换一个简单的样例以确保正确性，并修正样例输出。 假设输入： 2 2 1 1 10 2 2 5 B(2,2) is blocked by A(1,1). Eff(1,1) = 10. Eff(2,2) = 5 - 10 = -5. Sum = 5.

再换一个： 3 3 1 1 1 2 2 2 3 3 3 Eff(1,1)=1 Eff(2,2)=2-1=1 Eff(3,3)=3-(1+2)=0 Sum = 2.

为了保险起见，我将重新设计一个符合逻辑的样例，并确保标程能算出正确结果。 新样例： N=4, M=3 (1, 1, 5) (2, 2, 10) (3, 3, 20)

Calc: Star 1 (1,1): No predecessors. Eff = 5. Star 2 (2,2): Predecessor (1,1). Sum_v = 5. Eff = 10 - 5 = 5. Star 3 (3,3): Predecessors (1,1), (2,2). Sum_v = 5 + 10 = 15. Eff = 20 - 15 = 5. Total = 5 + 5 + 5 = 15.

让我们用这个作为样例1。

4 3
1 1 5
2 2 10
3 3 20

15

数据范围与提示

对于 $100\%$ 的数据，保证：

• $1 \le N \le 10^5$
• $1 \le M \le 10^5$
• $1 \le x_i, y_i \le N$
• $1 \le v_i \le 10^9$
• 所有 $(x_i, y_i)$ 互不相同。

提示： 本题是一个典型的二维偏序问题。可以通过对 $x$ 坐标排序，然后使用树状数组（BIT）维护 $y$ 坐标上的前缀和来解决。 具体步骤：

1. 将所有恒星按 $x$ 坐标升序排序。如果 $x$ 相同，按 $y$ 坐标升序排序。
2. 遍历排序后的恒星列表。对于当前恒星 $(x, y, v)$，查询树状数组中 $[1, y-1]$ 区间的和，记为 $S$。这就是所有满足 $x_A < x$ 且 $y_A < y$ 的恒星的亮度之和。 注意：由于我们按 $x$ 排序遍历，当我们处理到某颗恒星时，树状数组中已经包含了所有 $x' < x$ 的恒星的信息。但是，如果有多个恒星具有相同的 $x$，我们需要小心处理“严格小于”的条件。
   • 如果题目要求 $x_A < x_B$，那么在处理同一 $x$ 值的恒星时，不能互相影响。因此，对于所有具有相同 $x$ 坐标的恒星，我们应该先查询它们的遮挡值（此时树状数组中只有 $x' < x$ 的数据），然后再统一将它们更新到树状数组中。
3. 累加每颗恒星的有效亮度 $v - S$ 到总答案中。
4. 最后对 $10^9+7$ 取模。