← 返回题目列表

Codeforces · 390/E

E. Inna 和大甜蜜矩阵

中文机器翻译题面 查看原题

Inna非常喜欢甜食。这就是为什么她想和迪玛和塞雷贾一起玩“甜蜜矩阵”游戏。但塞雷贾是个大人物,所以这场比赛对他来说意义不大。 Sereja 建议玩“大甜蜜矩阵”游戏。

“Large Sweet Matrix” 游戏场是一个 n × m 矩阵。让我们将矩阵的行从 1 到 n 编号,将列从 1 到 m 编号。我们将第 i 行第 j 列中的单元格表示为 (i, j)。矩阵的每个单元格可以包含多个糖果,最初所有单元格都是空的。游戏分 w 步进行,每一步都会发生以下两个事件之一:

1. Sereja 选择 5 个整数 x1, y1, x2, y2, v (x1 ≤ x2, y1 ≤ y2) 并向每个矩阵单元 (i, j) 添加 v 颗糖果(x1 ≤ i ≤ x2;y1 ≤ j ≤ y2)。
2. Sereja 选择四个整数 x1, y1, x2, y2 (x1 ≤ x2, y1 ≤ y2)。然后他要求 Dima 计算单元格 (i, j) (x1 ≤ i ≤ x2; y1 ≤ j ≤ y2) 中的糖果总数,并要求 Inna 计算矩阵 (p, q) 单元格中的糖果总数,满足以下逻辑标准: (p < x1 OR p > x2) AND (q < y1 或 q > y2)。最后,Sereja 要求写下 Dima 计算出的数字与 Inna 计算出的数字之间的差值 (D - I)。

不幸的是,Sereja 的矩阵实在是太大了。这就是为什么伊娜和迪玛无法应对算计的原因。帮助他们!

输入

输入的第一行包含三个整数 n、m 和 w (3 ≤ n, m ≤ 4·106; 1 ≤ w ≤ 105)。

接下来的 w 行描述了游戏中的动作。

- 描述第一类型事件的行包含 6 个整数:0、x1、y1、x2、y2 和 v (1 ≤ x1 ≤ x2 ≤ n;1 ≤ y1 ≤ y2 ≤ m;1 ≤ v ≤ 109)。
- 描述第二类型事件的行包含 5 个整数:1、x1、y1、x2、y2 (2 ≤ x1 ≤ x2 ≤ n - 1;2 ≤ y1 ≤ y2 ≤ m - 1)。

保证第二种类型的移动至少发生一次。保证单次操作添加的糖果不会超过109颗。

注意,约束非常大,所以请使用最优的数据结构。最大测试将在预测试中进行。

输出

对于每第二个类型 move,在一行上打印一个整数 - Dima 和 Inna 的数字之间的差异。

示例

输入 #1

4 5 5
0 1 1 2 3 2
0 2 2 3 3 3
0 1 5 4 5 1
1 2 3 3 4
1 3 4 3 4

输出 #1

2
-21

注意

示例注释。第一次查询后,矩阵如下所示:

第二个之后是:

第三个之后是:

对于第四个查询,Dima 的总和等于 5 + 0 + 3 + 0 = 8,Inna 的总和等于 4 + 1 + 0 + 1 = 6。查询的答案等于 8 - 6 = 2。对于第五个查询,Dima 的总和等于 0,Inna 的总和等于 18 + 2 + 0 + 1 = 21。答案查询结果为 0 - 21 = -21。