← 返回比赛

已结束 COCR Cup 2025

← 上一题下一题 →

A5142 | $Farm$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

题目背景 $\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$，输出其采摘蔬菜的数量。

输入输出样例

输入 #1

输出 #1

1
0

【数据范围】 对于 $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$A7~9$10^3$$10^5$B10~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$

C++ 编辑器

输入

输出