棋盘滤镜：明暗差值

故事背景

一款照片后期软件提供了“棋盘滤镜”：它在图像网格上交替增强与减弱亮度。为了评估滤镜效果，工程师需要计算任意矩形区域内“增强像素之和减去减弱像素之和”的差值。

题目描述

给定一个 n×m 的整数矩阵 a 表示像素强度。定义在 1 基坐标下，若 (i+j) 为偶数则该格为“明”（加号），若 (i+j) 为奇数则该格为“暗”（减号）。

有 q 次询问，每次给出矩形 (x1, y1) 到 (x2, y2)。请输出该矩形内“明格子的数值之和 − 暗格子的数值之和”的结果。

输入格式

• 第一行包含三个整数 n、m、q。
• 接下来 n 行，每行 m 个整数，表示矩阵 a。
• 接下来 q 行，每行四个整数 x1、y1、x2、y2。

输出格式

输出 q 行，每行一个整数，表示对应矩形的明暗差值。

输入输出样例 #1

输入 #1

2 3 2
1 2 3
4 5 6
1 1 2 3
1 2 2 3

输出 #1

-3
0

样例解释 #1

在 1 基下，(i+j) 偶数为明、奇数为暗。第一问区域内明暗差值为 (1-2+3-4+5-6) = -3；第二问为 (2-3+5-6)= -2，但注意坐标覆盖 (1,2)-(2,3) 的四格中明暗分布为 {暗,明;明,暗}，计算为 (−2+3+5−6)=0。

说明/提示

• 数据范围示例：1 ≤ n,m ≤ 1000；1 ≤ q ≤ 2×10^5；-10^9 ≤ a[i][j] ≤ 10^9。
• 思路提示：可构造新矩阵 b[i][j] = a[i][j] * ( ( (i+j) % 2 == 0 ) ? 1 : -1 )，对 b 做二维前缀和后即可 O(1) 回答查询。