#400. 月光灯阵大修复(二维 vector)

月光灯阵大修复(二维 vector)

月光灯阵大修复(二维 vector)

题目描述

在星际补给站的第二层,武锦澄、曹智钦、崔馨月、包瑞鑫、宋奕霏发现了一块由 nn 行 mm 列灯泡组成的长方形月光灯阵,每个灯泡有一个非负整数亮度。

为了让灯阵重新点亮,五位队员使用了五种维修指令:

  • W x y v:武锦澄将第 x 行、第 y 列灯泡的亮度修改为 v。
  • C x1 y1 x2 y2:曹智钦测量行号从 x1 到 x2、列号从 y1 到 y2 的整个矩形中亮度的总和,输出这个整数。四条边界都包含在内。
  • X r:崔馨月把第 r 行的灯泡顺序左右翻转。例如 [1,2,3] 变为 [3,2,1]。
  • B c:包瑞鑫把第 c 列的灯泡顺序上下翻转。
  • S x y:宋奕霏读出坐标 (x,y) 的灯泡当前亮度,输出这个整数。

所有操作按顺序执行,位置始终从 1 开始编号。行翻转或列翻转以后,灯泡的位置会改变,后续指令操作的是翻转后的当前位置。

输入格式

第一行包含三个整数 n m q,分别表示行数、列数和操作次数。

接下来 n 行,每行 m 个非负整数,表示初始灯阵。

接下来 q 行,每行是一条上述五种操作之一。

输出格式

对每个 C 或 S 指令,按指令出现的顺序输出一行整数。其他指令无需输出。

数据范围

  • 1≤n,m≤501\le n,m\le 50,1≤q≤20001\le q\le 2000。
  • 灯泡亮度始终在 [0,109][0,10^9] 内。
  • 所有输入坐标合法;对 C 指令有 1≤x1≤x2≤n1\le x1\le x2\le n、1≤y1≤y2≤m1\le y1\le y2\le m。
  • 矩形和可能超过 32 位整数范围,请使用 64 位整数。

输入样例

2 3 8
1 2 3
4 5 6
C 1 1 2 3
X 1
S 1 1
B 2
C 1 2 2 3
W 2 1 9
C 2 1 2 3
S 2 2

输出样例

21
3
14
17
2

样例说明

第 1 行左右翻转后,灯阵变为:

3 2 1
4 5 6

再把第 2 列上下翻转,灯阵变为:

3 5 1
4 2 6

其后的矩形求和和单点查询都基于当前灯阵。

学习提示

本题适合使用 vector<vector<long long>> 保存二维网格。第 x 行可以用一维 vector 处理;第 c 列可以通过交换不同行、相同列的元素来翻转。数据范围允许直接双重循环计算矩形和。