「POI 2020/2021 R1」Tablica binarna 题解

算法思路

本题使用二维差分和奇偶性分析的巧妙方法来解决矩阵翻转问题。核心思想是将矩形翻转操作转化为四个角的异或操作。

关键观察

1. 二维差分定义

定义差分矩阵 $d$：

• $d[i][j] = A[i][j] \oplus A[i-1][j] \oplus A[i][j-1] \oplus A[i-1][j-1]$
• 其中 $\oplus$ 表示异或运算

2. 矩形翻转的差分性质

对于矩形翻转操作 $(i_1, j_1, i_2, j_2)$，只需要修改四个角：

op(x1, y1);    // d[i1][j1] ^= 1
op(x1, y2);    // d[i1][j2+1] ^= 1  
op(x2, y1);    // d[i2+1][j1] ^= 1
op(x2, y2);    // d[i2+1][j2+1] ^= 1

3. 简单操作与差分的关系

关键定理：需要的简单操作次数等于差分矩阵中 $1$ 的个数。

代码解析

差分矩阵维护

int d[N][N];  // 二维差分矩阵
int ans = 0;  // 当前差分矩阵中1的个数

操作函数

auto op = [&](int x, int y) {
    if (!x || !y) return;  // 边界检查
    
    ans -= d[x][y];        // 移除旧值贡献
    d[x][y] ^= 1;          // 翻转该位置
    ans += d[x][y];        // 添加新值贡献
};

处理每个查询

while (q--) {
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    x1--, y1--;  // 转换为0-indexed，便于差分计算
    
    // 更新四个角
    op(x1, y1);
    op(x1, y2);
    op(x2, y1);
    op(x2, y2);
    
    cout << ans << "\n";  // 输出当前简单操作次数
}

算法正确性证明

1. 差分矩阵的性质

• 原矩阵 $A$ 可以通过二维前缀异或从 $d$ 恢复
• $A[i][j] = \bigoplus_{x=1}^i \bigoplus_{y=1}^j d[x][y]$

2. 矩形翻转的等价性

翻转矩形 $[i_1, i_2] \times [j_1, j_2]$ 等价于：

• 在差分矩阵中翻转四个角 $(i_1, j_1), (i_1, j_2+1), (i_2+1, j_1), (i_2+1, j_2+1)$

3. 简单操作的作用

简单操作 $(1,1,i,j)$ 翻转矩形 $[1,i] \times [1,j]$，在差分矩阵中只影响位置 $(i,j)$。

复杂度分析

• 时间复杂度：$O(1)$ 每次操作（只修改4个位置）
• 空间复杂度：$O(nm)$
• 总复杂度：$O(q)$