/ SB域 / 题库 /

二维数列 (U50446)

二维数列 (U50446)

Background

对于一维的数列,我们可以通过一些神奇的数据结构来维护。

然而对于二维的数组这样的方法则需要拓宽视角,或者说需要有更高妙的算法了

现在让你来解决这样一个数据结构的问题。

Description

你需要维护一个数据结构。

支持下列操作:

  • F x y 询问单点(x,y)的值

  • Q x1 y1 x2 y2 询问一个对角线顶点分别为(x1,y1)(x2,y2)的矩形的面积

  • A x1 y1 x2 y2 d 将一个对角线顶点分别为(x1,y1)(x2,y2)的矩形中所有元素加d

  • D x1 y1 x2 y2 d 将一个对角线顶点分别为(x1,y1)(x2,y2)的矩形中所有元素减d

  • E 结束所有输入。您的程序需要立即退出,之后所有的操作应该不做处理

Format

Input

第1行两个正整数n,m表示整个矩形的宽和长

第2行开始到第n+1行每一行m个整数描述整一个矩形

第n+2行开始描述若干个操作,操作类型对于上面的F Q A D E

Output

对于每一次Q或者F操作输出对应的值表示询问的结果

对于100%的数据 可以保证询问的结果和中间变量在long long范围内

Sample 1

Input

4 4
1 1 2 4
7 9 3 -1
7 6 5 9
6 6 5 4
Q 1 1 4 4
A 1 2 3 4 5
Q 1 1 4 4
A 2 3 4 4 -5
Q 1 1 4 4
D 2 2 3 3 -1
Q 1 1 4 4
F 1 1
E
Q 1 1 4 4

Output

74
119
89
93
1

Limitation

数据范围和约定如下表所示:

信息

难度
10
分类
(无)
标签
(无)
递交数
10
已通过
0
通过率
0%
上传者