Skip to content

11630: 【原1630】Fast Matrix Operations

题目

题目描述

author: TA 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1630

Description

一个r行c列的全零矩阵,支持以下4种操作。

  1. 1 x1 y1 x2 y2 v 表示子矩阵(x1, y1, x2, y2)的所有元素增加v(v > 0)
  2. 2 x1 y1 x2 y2 v 表示子矩阵(x1, y1, x2, y2)的所有元素设为v(v > 0)
  3. 3 x1 y1 x2 y2 查询子矩阵(x1, y1, x2, y2)的所有元素的和
  4. 4 x1 y1 x2 y2 查询子矩阵(x1, y1, x2, y2)中的最小值和最大值

子矩阵(x1, y1, x2, y2)是指满足x1 <= x <= x2, y1 <= y <= y2的所有元素(x, y)。

Input Format

第一行三个整数r, c, m,其中m是操作的个数。接下来m行,每行一个操作。

Output Format

对于每一个第三种操作,给出所查询的子矩阵中的所有元素的和。对于每一个第四种操作,给出所查询的子矩阵中的最小值和最大值。

Sample Input

4 4 8 
1 1 2 4 4 5 
3 2 1 4 4 
4 2 1 4 4 
1 1 1 3 4 2 
3 1 2 4 4 
4 1 2 4 4 
3 1 1 3 4 
4 1 1 3 4

Sample Output

45 
0 5 
78 
5 7 
69 
2 7

数据范围

  • 对于40%的数据,c <= 300, m <= 300;
  • 对于另外20%的数据,c <= 20000, m <= 50000, 保证操作一、二中的 y1==y2,并且没有第四种操作;
  • 对于另外20%的数据,c <= 20000, m <= 50000, 保证操作一、二中的 y1==y2;
  • 对于100%的数据,r <= 20, c <= 20000, m <= 50000。
  • 数据保证任意时刻矩阵所有元素之和不超过10^9。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!