AdditionalFile5664.zip

#5664. 「JOI 2026 Final Day1」庭园 3

标签: 传统 | 时间限制: 4000 ms | 内存限制: 1024 MiB |

题目描述

题目译自 JOI 2026 Final Day1 T2 「庭園 3 / Garden 3」

JOI 庭园是一个长方形，被划分为 $H$ 行 $W$ 列的网格。从上数第 $i$ 行、从左数第 $j$ 列的格子被称为区块 $(i, j)$。

当某个区块下雨时，该区块的水分量会增加。除了下雨之外，区块的水分量不会发生变化。水分量达到 $X$ 或以上的区块会变得泥泞，十分危险。因此，作为 JOI 庭园管理者的 JOI 君，在每天早晨都会设定一个包含所有水分量在 $X$ 或以上的区块的长方形禁区。确切地说，他会选择四个整数 $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$ 天，每天傍晚 JOI 庭园都会下一场雨。在距今 $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, \dots, N$，请编写一个程序，求出第 $k$ 天过后的次日早晨 JOI 君设定的禁区所含区块数量的最小可能值。

输入格式

第一行包含四个整数 $H,W,N,X$。

接下来的 $N$ 行，每行包含五个整数 $U_i,D_i,L_i,R_i,C_i$。

输出格式

向标准输出输出 $N$ 行。第 $k$ 行 $(1 \leq k \leq N)$ 应输出第 $k$ 天过后的次日早晨 JOI 君设定的禁区所含区块数量的最小可能值。

样例 1

输入

3 3 5 10
3 3 1 1 5
1 3 1 2 7
1 3 3 3 4
1 1 1 2 12
3 3 3 3 6

输出

0
1
1
6
9

以下是每天水分量的增加情况以及使包含的区块数量最小的禁区设定方法示例：

• 第 $1$ 天傍晚（距今 $0$ 天后），区块 $(3, 1)$ 的水分量增加 $5$。在次日早晨，没有任何区块的水分量达到 $10$ 或以上，因此不设定禁区。
• 第 $2$ 天傍晚（距今 $1$ 天后），区块 $(1, 1), (1, 2), (2, 1), (2, 2), (3, 1), (3, 2)$ 的水分量分别增加 $7$。在次日早晨，水分量在 $10$ 或以上的区块是区块 $(3, 1)$。JOI 君通过选择 $u=d=3, l=r=1$，可以设定一个包含 $1$ 个区块的禁区。
• 第 $3$ 天傍晚（距今 $2$ 天后），区块 $(1, 3), (2, 3), (3, 3)$ 的水分量分别增加 $4$。在次日早晨，水分量在 $10$ 或以上的区块仍只有区块 $(3, 1)$。JOI 君通过选择 $u=d=3, l=r=1$，可以设定一个包含 $1$ 个区块的禁区。
• 第 $4$ 天傍晚（距今 $3$ 天后），区块 $(1, 1), (1, 2)$ 的水分量分别增加 $12$。在次日早晨，水分量在 $10$ 或以上的区块是 $(1, 1), (1, 2), (3, 1)$。JOI 君通过选择 $u=1, d=3, l=1, r=2$，可以设定一个包含 $6$ 个区块的禁区。
• 第 $5$ 天傍晚（距今 $4$ 天后），区块 $(3, 3)$ 的水分量增加 $6$。在次日早晨，水分量在 $10$ 或以上的区块是 $(1, 1), (1, 2), (3, 1), (3, 3)$。JOI 君通过选择 $u=1, d=3, l=1, r=3$，可以设定一个包含 $9$ 个区块的禁区。

此样例满足子任务 $3, 4, 5$ 的限制。

样例 2

输入

9 1 5 1
3 3 1 1 4
5 8 1 1 1
3 5 1 1 3
8 8 1 1 4
8 9 1 1 5

输出

1
6
6
6
7

此样例满足所有子任务的限制条件。

样例 3

输入

4596 9794 15 141929907
600 3070 2222 8763 472026497
47 2644 3276 6033 930213777
638 945 304 1100 992702990
370 2211 2178 2977 783902937
277 2601 1559 8989 842013671
566 3272 3124 8456 254633541
91 4241 2655 8035 303526265
1342 3662 3909 7175 685435928
1176 4012 2827 8429 614977118
255 2461 1482 5835 794902067
982 2314 941 3952 342731056
1603 2215 6730 7105 332440107
2301 4568 6898 9561 591652619
124 2097 3520 8882 168525684
1845 3599 5592 7145 555656973

输出

16165282
19783008
25583040
25583040
26266464
28021036
36437770
36437770
36437770
36437770
36437770
36437770
41864676
41864676
41864676

此样例满足子任务 $3, 4, 5$ 的限制条件。

数据范围与提示

对于所有输入数据，满足：

• $1 \leq H \leq 10^{9}$。
• $1 \leq W \leq 10^{9}$。
• $1 \leq N \leq 200000$。
• $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)$。
• 输入的所有值均为整数。

详细子任务附加限制及分值如下表所示。