二维数列 (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%
- 上传者