【MX-J8-T3】水星湖

原题链接：<https://oier.team/problems/83>。

有一个 $n\times m$ 的矩形网格。用数对 $(x, y)$ 表示第 $x$ 行、第 $y$ 列的位置。 网格内有 $q$ 片湖泊（$q$ 可能为 $0$），第 $i$ 片湖泊覆盖了左上角为 $(a_{i, 1}, b_{i, 1})$、右下角为 $(a_{i, 2}, b_{i, 2})$ 的矩形区域，这片区域里的所有位置都被称为湖泊。如果一个位置不属于任何一片湖泊，它就是陆地。湖泊两两不会重叠，但可能相邻。 小 Y 会进行 $r$ 次种树。第 $i$ 次，他在第 $t_i$ 秒向 $(x_i, y_i)$ 里种下一棵树，保证该位置不为湖泊，且要么没有种下或生长过树，要么曾经种下或生长的树已经死亡。保证种树是按照时间顺序进行的，即 $t_1, t_2, \dots, t_r$ 单调不降。 每一秒，对于每个位置 $(x, y)$，若它同时满足如下所有条件，则会在 $(x, y)$ 处生长出一棵树： - 它是一块无树存活的陆地； - 它与一块湖泊**相邻**； - 它**在前一秒**与一棵存活的树**相邻**。 （上述所说的**相邻**是在四连通意义下的，即位置 $(x_1, y_1)$ 和 $(x_2, y_2)$ 相邻当且仅当 $\lvert x_1 - x_2 \rvert + \lvert y_1 - y_2 \rvert = 1$。） 如果一棵树在存活**大于 $\bm k$ 秒**后（以其被种下或生长出来时开始计算），与其相邻的所有位置**均为无树存活的陆地**，则它会死亡。 小 Y 想要知道：经过充分多时间后（也即，经过足够多的时间，使得网格内不会有新的位置长出树，也不会有旧的树死去的状态下），网格内最终会有多少棵树。

第一行，五个整数 $n, m, q, r, k$。 接下来 $q$ 行，每行四个正整数 $a_{i, 1}, b_{i, 1}, a_{i, 2}, b_{i, 2}$，描述第 $i$ 片湖泊的位置。保证湖泊两两不会重叠。 接下来 $r$ 行，每行三个正整数 $t_i, x_i, y_i$，分别表示第 $i$ 棵树被种下的秒数和行列位置。保证 $t_1, t_2, \dots, t_r$ 单调不降。

仅一行一个整数，表示经过充分多时间后，网格内最终会有多少棵树。

5 6 2 1 1
2 1 3 3
3 5 5 6
1 1 5

10

3 3 0 3 1
1 3 1
2 1 1
3 2 1

2

**【样例解释 \#1】** 如图所示，为经过充分多时间后网格中的情况。  网格内不会有新的位置长出树，也不会有旧的树死去，所以经过充分多时间后，网格内有 $10$ 棵树。 **【样例解释 \#2】** 在这一组数据中，所有位置都是陆地，没有湖泊。 第 $1$ 秒时，第一棵树在 $(3, 1)$ 被种下。 第 $2$ 秒时，第二棵树在 $(1, 1)$ 被种下。紧接着，第一棵树已存活 $> 1$ 秒，且与其相邻的所有位置均为没有存活的树的陆地，因此死亡。 第 $3$ 秒时，第三棵树在 $(2, 1)$ 被种下。紧接着，第二棵树已存活 $> 1$ 秒，而此时第三棵树与其相邻，因此不死亡。 随后，网格内不会有新的位置长出树，也不会有旧的树死去。所以经过充分多时间后，网格内有 $2$ 棵树。 **【样例 \#3】** 见附件中的 `lake/lake3.in` 与 `lake/lake3.ans`。 该组样例满足测试点 $4 \sim 7$ 的约束条件。 **【样例 \#4】** 见附件中的 `lake/lake4.in` 与 `lake/lake4.ans`。 该组样例满足测试点 $8 \sim 10$ 的约束条件。 **【样例 \#5】** 见附件中的 `lake/lake5.in` 与 `lake/lake5.ans`。 该组样例满足测试点 $13 \sim 15$ 的约束条件。 **【样例 \#6】** 见附件中的 `lake/lake6.in` 与 `lake/lake6.ans`。 该组样例满足测试点 $16 \sim 20$ 的约束条件。 **【数据范围】** 本题共 $20$ 个测试点，每个 $5$ 分。 |测试点编号|$n,m\le$|$q\le$|$r\le$|$t_i,k\le$| | :-----------: | :-------------:|:-----------: |:-----------: |:-----------: | |$1\sim3$|$10$|$10$|$10$|$10$| |$4\sim7$|$50$|$100$|$1000$|$1000$| |$8\sim 10$|$3000$|$0$|$10^5$|$10^9$| |$11\sim12$|$3000$|$10^5$|$1$|$10^9$| |$13\sim15$|$1000$|$10^5$|$10^5$|$12$| |$16\sim20$|$3000$|$10^5$|$10^5$|$10^9$| 对于全部数据，保证： - $1 \leq n, m \leq 3000$； - $0 \leq q \leq 10^5$； - $1 \leq a_{i, 1} \le a_{i, 2} \leq n$，$1 \leq b_{i, 1} \le b_{i, 2} \leq m$； - 湖泊两两不会重叠； - $1 \leq r \leq 10^5$； - $1 \leq t_1 \leq t_2 \leq \dots \leq t_r \leq 10^9$； - $1 \leq x_i \leq n$，$1 \leq y_i \leq m$； - 位置 $(x_i, y_i)$ 不是湖泊且无树存活； - $1 \leq k \leq 10^9$。