分析题意与解题方法

题目描述

给定一个 $N \times N$ 矩阵 $A$，初始值均为 $0$。支持以下两种操作：

1. $C\ x1\ y1\ x2\ y2$：将左上角 $(x1, y1)$ 和右下角 $(x2, y2)$ 的矩形区域的所有元素取反。
2. $Q\ x\ y$：查询矩阵中 $(x, y)$ 位置的值。

数据范围

• 测试用例数量：$X \leq 10$
• 矩阵大小：$2 \leq N \leq 1000$
• 操作总数：$1 \leq T \leq 50000$

解题思路

关键点

1. 高效更新：每次操作需要更新一个矩形区域，直接遍历会超时，因此需要使用 二维差分数组 技巧。
2. 查询优化：通过前缀和快速获取任意位置的值。

实现步骤

1. 初始化：

   • 定义二维差分数组 $c$，用于记录每个点的增量。
   • 初始化时将所有差分数组清零。

2. 更新操作：

   • 对于矩形区域 $(x1, y1)$ 到 $(x2, y2)$，通过差分数组更新四个关键点：
     • $(x1, y1)$：增加 $1$
     • $(x1, y2+1)$：减少 $1$
     • $(x2+1, y1)$：减少 $1$
     • $(x2+1, y2+1)$：增加 $1$
   • 这种更新方式保证了矩形区域内的值被正确翻转。

3. 查询操作：

   • 通过二维前缀和计算任意位置的值：$$\text{sum}(i, j) = \text{sum}(i-1, j) + \text{sum}(i, j-1) - \text{sum}(i-1, j-1) + c[i][j] $$
   • 如果 $\text{sum}(x, y)$ 为奇数，则当前位置为 $1$；否则为 $0$。

标程

#include <cstdio>
#include <cstring>
#define MAX 1024

int N, T, c[MAX][MAX] = {0};

// 获取最低位的 1
inline int lowbit(int x) { return x & -x; }

// 初始化差分数组
void init() {
    for (int i = 1; i <= N; ++i)
        memset(c[i] + 1, 0, N * sizeof(int));
}

// 更新差分数组
void update(int i, int j) {
    for (int x = i; x; x -= lowbit(x))
        for (int y = j; y; y -= lowbit(y))
            ++c[x][y];
}

// 查询前缀和
int query(int i, int j) {
    int sum = 0;
    for (int x = i; x <= N; x += lowbit(x))
        for (int y = j; y <= N; y += lowbit(y))
            sum += c[x][y];
    return sum;
}

int main() {
    int test, a, b, c, d;
    char s[4];
    for (scanf("%d", &test); test--; ) {
        scanf("%d%d", &N, &T);
        init();
        while (T--) {
            scanf("%s%d%d", s, &a, &b);
            if (s[0] == 'C') {
                scanf("%d%d", &c, &d);
                // 更新差分数组
                update(c, b - 1);
                update(a - 1, d);
                update(a - 1, b - 1);
                update(c, d);
            } else {
                // 查询结果并输出
                printf("%d\n", query(a, b) & 1 ? 1 : 0);
            }
        }
        puts(""); // 每个测试用例后输出空行
    }
    return 0;
}