AT_joi2026final_b 庭園 3 (Garden 3)

JOI 园是一个被分成 $H$ 行 $W$ 列方格的矩形区域。自上而下第 $i$ 行，从左到右第 $j$ 列的格子称为格子 $(i, j)$。 当雨水落在某格子上时，该格子的湿度会增加。除下雨以外，格子的湿度不会发生变化。如果某格子的湿度达到至少 $X$，该格子就会变成泥地，变得危险。因此，每天早上，JOI 园的管理员 JOI-kun 可以设定至多一个包含所有湿度至少为 $X$ 的格子的矩形禁入区域。更准确地说，JOI-kun 会选择四个整数 $u, d, l, r$（$1 \leq u \leq d \leq H, 1 \leq l \leq r \leq W$），禁入区域是所有满足 $u \leq i \leq d$ 且 $l \leq j \leq r$ 的格子 $(i, j)$。 初始时，JOI 园中所有格子的湿度均为 $0$。 从今天开始，将连续 $N$ 天，每天傍晚下雨一次。在第 $k-1$ 天傍晚（$1 \leq k \leq N$），对于所有满足 $U_k \leq i \leq D_k$ 且 $L_k \leq j \leq R_k$ 的格子 $(i, j)$，其湿度增加 $C_k$。 对于每一天 $k = 1, 2, \ldots, N$，请编写程序求出 JOI-kun 在第 $k$ 天早晨能设定的禁入区域包含的格子的最小可能数量。 ---

从标准输入读取如下数据。 > $H$ $W$ $N$ $X$ $U_1$ $D_1$ $L_1$ $R_1$ $C_1$ $U_2$ $D_2$ $L_2$ $R_2$ $C_2$ $\vdots$ $U_N$ $D_N$ $L_N$ $R_N$ $C_N$ ---

输出 $N$ 行到标准输出。第 $k$ 行（$1 \leq k \leq N$）输出 JOI-kun 在第 $k$ 天早晨能设定的禁入区域所包含的最小可能格子数。 ---

### 子任务 1.（$3$ 分）$X=1$。 2.（$24$ 分）$W=1$。 3.（$15$ 分）$N \leq 300$。 4.（$30$ 分）$N \leq 5\,000$。 5.（$28$ 分）无额外约束。 --- ### 样例解释 1 以下是每天湿度变化的一个例子，以及如何选择禁入区域使得所包含格子数最少。 - 第 $0$ 天傍晚，格子 $(3,1)$ 的湿度增加 $5$。第 $1$ 天早晨，湿度至少为 $10$ 的格子不存在，因此不设禁入区域。 - 第 $1$ 天傍晚，格子 $(1,1)、(1,2)、(2,1)、(2,2)、(3,1)、(3,2)$ 的湿度各自增加 $7$。第 $2$ 天早晨，格子 $(3,1)$ 的湿度达到至少 $10$。JOI-kun 选择 $u=d=3$ 且 $l=r=1$，禁入区域包含 $1$ 个格子。 - 第 $2$ 天傍晚，格子 $(1,3)、(2,3)、(3,3)$ 的湿度各自增加 $4$。第 $3$ 天早晨，格子 $(3,1)$ 的湿度仍然至少为 $10$。JOI-kun 选择 $u=d=3$ 且 $l=r=1$，禁入区域包含 $1$ 个格子。 - 第 $3$ 天傍晚，格子 $(1,1)、(1,2)$ 各自增加 $12$。第 $4$ 天早晨，格子 $(1,1)、(1,2)、(3,1)$ 的湿度都至少为 $10$。JOI-kun 选择 $u=1$、$d=3$、$l=1$、$r=2$，禁入区域包含 $6$ 个格子。 - 第 $4$ 天傍晚，格子 $(3,3)$ 的湿度增加 $6$。第 $5$ 天早晨，格子 $(1,1)、(1,2)、(3,1)、(3,3)$ 的湿度达到至少 $10$。JOI-kun 选择 $u=1$、$d=3$、$l=1$、$r=3$，禁入区域包含 $9$ 个格子。 该样例输入满足子任务 3、4、5 的约束。 --- ### 样例解释 2 本样例输入满足所有子任务的约束。 --- ### 样例解释 3 本样例输入满足子任务 3、4、5 的约束。 ### 约束条件 - $1 \leq H \leq 10^9$。 - $1 \leq W \leq 10^9$。 - $1 \leq N \leq 200\,000$。 - $1 \leq X \leq 2\times 10^{14}$。 - $1 \leq U_k \leq D_k \leq H$（$1 \leq k \leq N$）。 - $1 \leq L_k \leq R_k \leq W$（$1 \leq k \leq N$）。 - $1 \leq C_k \leq 10^9$（$1 \leq k \leq N$）。 - 所有给定值均为整数。 由 ChatGPT 5 翻译