AT_joi2026final_g 三角形降雨 (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$ 时各小区域及格点的示意图：  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,\ldots,K$，有多少个小区域在至少 $k$ 天内预计会下雨。 给定 JOI 国的大小、天气预报和 $K$，请编写程序，对于每个 $k=1,2,\ldots,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. ($4$ 分) $N = 2$，$K = 2$。 2. ($5$ 分) $L\leq 100$，$N\leq 100$。 3. ($5$ 分) $L\leq 1\,000$。 4. ($7$ 分) $N\leq 2\,000$。 5. ($10$ 分) $X_i = 0$（$1\leq i\leq N$），$K = 1$。 6. ($10$ 分) $X_i = 0$（$1\leq i\leq N$）。 7. ($23$ 分) $K = 1$。 8. ($18$ 分) $K \leq 2$。 9. ($18$ 分) 无更多约束。 --- ### 样例解释 1 对每个小区域，统计下雨天数，得到下图：  该样例输入满足子任务 $1, 2, 3, 4, 8, 9$ 的限制。 --- ### 样例解释 2 对每个小区域，统计下雨天数，得到下图：  该样例输入满足子任务 $2, 3, 4, 9$ 的限制。 ### 约束条件 - $2\leq L\leq 10^9$。 - $2 \leq N \leq 200\,000$。 - $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$）。 - 所有输入值均为整数。 由 ChatGPT 5 翻译