P15945 [JOI Final 2026] 雨落三角 / Triangular Rainfall

JOI 国是一个边长为 $L$ 的正三角形，其顶点为点 $A, B$ 和 $C$。这里 $L$ 是一个正整数。边 $AB$ 在东西方向上连接顶点 $A$ 和 $B$，顶点 $A$ 是 JOI 国最西端的一点，而顶点 $B$ 是最东端的一点。顶点 $C$ 是 JOI 国最北端的一点。 JOI 国被划分为 $L^2$ 个区域，每个区域都是一个边长为 $1$ 的正三角形。作为某个区域顶点的点被称为格点。对于满足 $0 \leq y \leq L$ 且 $0 \leq x \leq L-y$ 的整数 $x, y$，从南数第 $(1+y)$ 个、从西数第 $(1+x)$ 个的格点记作 $(x, y)$。特别地，$A, B$ 和 $C$ 分别记作 $(0,0), (L, 0)$ 和 $(0, L)$。例如，下图显示了 $L=5$ 时的区域和格点。 ::::align{center}  :::: 在 JOI 国，已经公布了未来 $N$ 天的天气预报。在第 $i$ 天，预报降雨将落在以格点 $(X_i, Y_i), (X_i + Z_i, Y_i)$ 和 $(X_i, Y_i + Z_i)$ 为顶点的三角形区域 $T_i$ 内。如果一个区域完整地包含在 $T_i$ 中，则称该区域在第 $i$ 天被预报有雨。 为了应对降雨引起的灾害，有必要针对每个 $k = 1, 2, \dots, K$，确定预报有至少 $k$ 天降雨的区域数量。 给定 JOI 国的大小、天气预报以及 $K$，请编写一个程序，对于每个 $k = 1, 2, \dots, K$，计算预报有至少 $k$ 天降雨的区域数量。

输入通过标准输入以以下格式给出： > $L$ $N$ $K$\ > $X_1$ $Y_1$ $Z_1$\ > $X_2$ $Y_2$ $Z_2$\ > $\vdots$\ > $X_N$ $Y_N$ $Z_N$

向标准输出打印 $K$ 行。第 $k$ 行（$1 \leq k \leq K$）应包含预报有至少 $k$ 天降雨的区域数量。

### 样例 1 如果我们图示每个区域预报有雨的天数，将得到下图。 ::::align{center}  :::: 该样例输入满足子任务 $1, 2, 3, 4, 8$ 和 $9$ 的限制条件。 ### 样例 2 如果我们图示每个区域预报有雨的天数，将得到下图。 ::::align{center}  :::: 该样例输入满足子任务 $2, 3, 4$ 和 $9$ 的限制条件。 ### 限制条件 - $2 \leq L \leq 10^{9}$。 - $2 \leq N \leq 200000$。 - $1 \leq K \leq 5$。 - $0 \leq X_i \leq L$ ($1 \leq i \leq N$)。 - $0 \leq Y_i \leq L$ ($1 \leq i \leq N$)。 - $1 \leq Z_i \leq L$ ($1 \leq i \leq N$)。 - $X_i + Y_i + Z_i \leq L$ ($1 \leq i \leq N$)。 - 所有输入值均为整数。 ### 子任务 1. (4 分) $N = 2, K = 2$。 2. (5 分) $L \le 100, N \le 100$。 3. (5 分) $L \le 1\,000$。 4. (7 分) $N \le 2\,000$。 5. (10 分) $X_i = 0$ $(1 \le i \le N), K = 1$。 6. (10 分) $X_i = 0$ $(1 \le i \le N)$。 7. (23 分) $K = 1$。 8. (18 分) $K \le 2$。 9. (18 分) 无额外限制。