A71103.Farm

题目背景

$\color{red}{\mathtt{FM}}$：“这么大片菜地，需要多少种子才能铺满呢？“

$\color{yellow}{\mathtt{NH}}$：“作为一名优秀的农场主，我们一定要使用……嘿嘿嘿……”

$\color{red}{\mathtt{FM}}$：“去去去！正经点！我们并没有穿越！”

$\color{yellow}{\mathtt{NH}}$：“行，那就只能用代码了。”

NH 被 FM 挖苦了，快帮助 NH 证明他的实力吧！

---

题目描述

现在有一块菜地，大小是 $N\times M$。每一次操作过后时间都会增加 $1$。

给定 $Q$ 次操作，每次操作是以下 $2$ 类操作之一：

• 1 x y k：表示在坐标 $(x,y)$ 洒一粒蔬菜种子，该种子 $k$ 个单位时间后会成熟。
• 2 x1 y1 x2 y2：表示采摘区间 $(x_1,y_1)$ 到 $(x_2,y_2)$ 之间所有成熟的蔬菜。

对于每个操作 $2$，你需要给出本次采摘蔬菜的数量。

输入共 $Q + 1$ 行：

第一行 $3$ 个正整数 $N,M,Q$ 表示菜地的大小和操作次数；

接下来 $Q$ 行每行若干个正整数表示一次操作。

对于每个操作 $2$，输出其采摘蔬菜的数量。

【数据范围】

对于 $100\%$ 的数据，保证：

• $1\le N,M \le 5\times 10^5$
• $1\le Q \le 2\times 10^5$
• 对于操作 $1$，$1\le x \le N$，$1\le y \le M$，$1\le k \le Q$
• 对于操作 $2$，$1\le x1 \le x2 \le N$，$1\le y1 \le y2 \le M$
• 同一格子最多有 $1$​ 个蔬菜
• 数据均为随机数据

测试点编号	$N,M\le$	$Q \le$	特殊性质
1~4	$10^3$	$10^3$	无
5~6	$10^3$	$10^5$	A
7~9	$10^3$	$10^5$	B
10~20	$5\times 10^5$	$2\times 10^5$	无

特殊性质 A：仅有一次操作 $2$ 且位于最后。

特殊性质 B：操作 $1$ 的 $k$ 值恒为 $1$。

【样例解释】

样例组 #1：我们有一个大小为 $3\times 3$ 的菜地，

操作 $1$： 在坐标 $(2,2)$ 洒一粒种子，成熟时间为 $1$ 单位时间。

• 当前时间：$1$
• 种子将在时间 $1 + 1 = 2$ 时成熟。

操作 $2$： 采摘矩形区域 $(1,1)$ 到 $(3,3)$ 的所有成熟蔬菜。

• 当前时间：$2$
• $(2,2)$ 的种子成熟时间为 $2=2$，因此被采摘。
• 采摘数量：$1$

操作 $1$： 在坐标 $(2,1)$ 洒一粒种子，成熟时间为 $3$ 单位时间。

• 当前时间：$3$
• 种子将在时间 $3 + 3 = 6$ 时成熟。

操作 $1$： 在坐标 $(3,3)$ 洒一粒种子，成熟时间为 $1$ 单位时间。

• 当前时间：$4$
• 种子将在时间 $4 + 1 = 5$ 时成熟。

操作 $2$： 采摘矩形区域 $(1,1)$ 到 $(2,2)$ 的所有成熟蔬菜。

• 当前时间：$5$
• $(2,2)$ 的种子已被采摘（不再重复计算）。
  $(2,1)$ 的种子成熟时间 $6 > 5$，未成熟。
• 采摘数量：$0$