同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

1636_二维树状数组3：区间修改，区间查询

2022-5-16 18:17| 发布者: Hocassian| 查看: 51| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-2-8950465004500-Problem List-采集的数据-后羿采集器.html

Pro.ID

1636

Title

二维树状数组 3：区间修改，区间查询

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=1636

AC

Submit

Ratio

时间&空间限制

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)

描述

这是一道模板题。

给定一个大小为 N × M 的零矩阵，直到输入文件结束，你需要进行若干个操作，操作有两类：

1 a b c d x，表示将左上角为 (a, b)，右下角为 (c, d) 的子矩阵全部加上 x；
2 a b c d，表示询问左上角为 (a, b)，右下角为 (c, d) 为顶点的子矩阵的所有数字之和。

输入

第一行一个字符和两个正整数，其中 n, m 分别表示矩阵的行数与列数。

接下来若干行直到文件结束，均代表你需要进行的操作。

对于 10% 的数据，1 ≤ n, m ≤ 16，操作不超过 200 个；

对于 60% 的数据，1 ≤ n, m ≤ 512 ；

对于 100% 的数据，1 ≤ n, m ≤ 2048,| x |≤ 500 ，操作不超过 2×10⁵ 个，保证运算过程中及最终结果均不超过 64 位带符号整数类型的表示范围，并且修改与查询的子矩阵存在。

输出

Description

这是一道模板题。

给定一个大小为 N × M 的零矩阵，直到输入文件结束，你需要进行若干个操作，操作有两类：

1 a b c d x，表示将左上角为 (a, b)，右下角为 (c, d) 的子矩阵全部加上 x；
2 a b c d，表示询问左上角为 (a, b)，右下角为 (c, d) 为顶点的子矩阵的所有数字之和。

Input

第一行一个字符和两个正整数，其中 n, m 分别表示矩阵的行数与列数。

接下来若干行直到文件结束，均代表你需要进行的操作。

对于 10% 的数据，1 ≤ n, m ≤ 16，操作不超过 200 个；

对于 60% 的数据，1 ≤ n, m ≤ 512 ；

Output

对于每个 2 操作，输出一行代表查询的结果。

Sample Input

4 4
1 1 1 3 3 2
1 2 2 4 4 1
2 2 2 3 3

Sample Output

样例输入