逃离魔爪

题目描述

安全穿过了雷区，你居然发现了一片农场，此时农场上十分热闹。

AuMiner 正在追捕一位在 QQ 农场偷菜的小偷 xyx，好不容易马上就要抓到 xyx 了，xyx 突然回头求饶不要抓我，AuMiner 回应道可以不抓你但是你必须回答我的一系列问题，小偷 xyx 紧张极了，你能帮助小偷 xyx 逃离 AuMiner 的魔爪吗？

Auminer 有一块 $n \times m$ 的矩形地块，一开始，里面所有的格子都写着 $0$，代表所有地都未锄好，而 $1$ 代表地已经锄好。

AuMiner 会有以下的操作和询问：

  • $1, x_1, y_1, x_2, y_2$, $(1 \leq x_1 \leq x_2 \leq n,1 \leq y1 \leq y_2 \leq m)$ 表示对 QQ 农场矩形范围左上角 $(x_1, y_1)$ 到右下角 $(x_2, y_2)$ 进行锄地，写有 $0$ 的田地会变成 $1$，写有 $1$ 的田地会变成 $0$。
  • $2, x_1, y_1, x_2, y_2$, $(1 \leq x_1 \leq x_2 \leq n,1 \leq y1 \leq y_2 \leq m)$ 表示询问 QQ 农场的矩形范围左上角 $(x_1, y_1)$ 到右下角 $(x_2, y_2)$ 中锄好的地的数量的奇偶值。

数据样例

输入

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

输出

1
2
1
0

二维树状数组 - $O(Q * log^2(N))$

题目的含义

给定一个二维 $01$ 矩阵，有 $q$ 次询问，每次询问给定一个矩阵 $(x_1, y_1, x_2, y_2)$ 表示矩阵左上角和右下角点分别为 $(x_1, y_1), (x_2, y_2)$：

  • $q = 1$：将当前矩阵中的所有 $01$ 进行翻转
  • $q = 2$：询问当前矩阵中 $1$ 的个数是奇数还是偶数

转换矩阵差分

首先，对 $01$ 矩阵翻转，可以直接将矩阵所有的值 $+1$ 即可，利用奇偶性判断 $01$，那么对一个矩阵同时加一个数，可以利用二维差分进行维护。记差分数组为 $w$

那么现在产生一个问题是：虽然利用差分可以维护每次修改后的矩阵的状态，那么对于每次询问矩阵的和，如果用差分维护的话，那么如何才能维护前缀和呢？

$PS:$ 这个题目还有一个一维版本，如果对一维版本理解的话，那么这个题目会好理解很多

二维前缀和表示

我们来分析一下如何用矩阵差分 $w$ 表示二维前缀和，我们要表示二维前缀和是矩阵 $(1, 1, x, y)$ 中所有元素的和，首先我们依次看这个矩阵中的每个点如何表示：

  • $(1, 1): w_{1, 1}$
  • $(1, 2): w_{1, 1} + w_{1, 2}$
  • $…$
  • $(2, 1): w_{1, 1} + w_{2, 1}$
  • $…$

将上面所有点对应的值全部加起来就是二维前缀和，那么我们可以观察每个 $w_{i, j}$ 被计算的次数：

  • $w_{1, 1}$: 矩阵中所有点的计算都包含，因此一共计算 $x * y$ 次 - 矩阵 $(1, 1, x, y)$ 一共有 $x * y$ 个点
  • $w_{1, 2}$: 所有在矩阵 $(1, 2, x, y)$ 中的点的值的计算都包括当前点，因此会计算 $x * (y - 1)$ 次
  • $…$

因此我们观察发现 $w_{i, j}$ 被计算的点是矩阵 $(i, j, x, y)$ 中的所有点，因此：

$w_{i, j}$ 被计算的次数是：$(x - i + 1) * (y - j + 1)$

那么现在我们可以表示二维前缀和了：
$$S_{x, y} = \sum_{i = 1} ^ n \sum_{j = 1} ^ m w_{i, j} * (x - i + 1) * (y - j + 1)$$

树状数组维护前缀和

我们知道上述式子是无法直接维护的，因为 $x, y$ 的值每次都是不一样的，因此需要对上述式子进行等价变换，我们记：$w_{i, j}$ 为 $w$：

$$\begin{aligned}
S_{x, y} & = \sum_{i = 1} ^ n \sum_{j = 1} ^ m w * (x - i + 1) * (y - j + 1) \\
& = \sum_{i = 1} ^ n \sum_{j = 1} ^ m (w * (x + 1) - w * i) * (y - j + 1) \\
& = \sum_{i = 1} ^ n \sum_{j = 1} ^ m (w * (x + 1) * (y + 1) - w * j * (x + 1) - w * i * (y + 1) + w * i * j) \\
\end{aligned}$$

此时，我们就可以维护这个式子了，利用 $4$ 个二维树状数组分为维护：$w$, $w * i$, $w * j$, $w * i * j$ 即可

时间复杂度

二维树状数组每次修改和查询的复杂度都是 $O(log^2(N))$，一共 $Q$ 次查询，因此复杂度是：$O(Q * log^2(N))$

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <unordered_map>
#include <unordered_set>
using namespace std;
using ull = unsigned long long;
using ll = long long;
using PII = pair<int, int>;
const double eps = 1e-8;
const double PI = acos(-1);
const int inf = 0x3f3f3f3f, INF = 0x3f3f3f3f3f3f3f3f;
const int N = 1006, M = 2000006;

#define x first
#define y second

int n, m;
int w[N][N];
int tr[N][N], tri[N][N], trj[N][N], trij[N][N];

int lowbit(int x) {
    return x & -x;
}

void add(int tr[][N], int x, int y, int c) {
    for (int i = x; i <= n; i += lowbit(i)) {
        for (int j = y; j <= m; j += lowbit(j)) {
            tr[i][j] += c;
        }
    }
}

int query(int tr[][N], int x, int y) {
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) {
        for (int j = y; j; j -= lowbit(j)) {
            res += tr[i][j];
        }
    }
    return res;
}

void insert(int x1, int y1, int x2, int y2, int c = 1) {
    add(tr, x1, y1, c), add(tr, x1, y2 + 1, c);
    add(tr, x2 + 1, y1, c), add(tr, x2 + 1, y2 + 1, c);
    
    add(tri, x1, y1, c * x1), add(tri, x1, y2 + 1, c * x1);
    add(tri, x2 + 1, y1, c * (x2 + 1)), add(tri, x2 + 1, y2 + 1, c * (x2 + 1));
    
    add(trj, x1, y1, c * y1), add(trj, x1, y2 + 1, c * (y2 + 1));
    add(trj, x2 + 1, y1, c * y1), add(trj, x2 + 1, y2 + 1, c * (y2 + 1));
    
    add(trij, x1, y1, c * x1 * y1), add(trij, x1, y2 + 1, c * x1 * (y2 + 1));
    add(trij, x2 + 1, y1, c * (x2 + 1) * y1), add(trij, x2 + 1, y2 + 1, c * (x2 + 1) * (y2 + 1));
}

int get_sum(int x, int y) {
    return query(tr, x, y) * (x + 1) * (y + 1)
        - query(tri, x, y) * (y + 1) 
        - query(trj, x, y) * (x + 1) 
        + query(trij, x, y);
}

int get_solve(int x1, int y1, int x2, int y2) {
    int res = get_sum(x2, y2) - get_sum(x2, y1 - 1) - get_sum(x1 - 1, y2) + get_sum(x1 - 1, y1 - 1);
    return res & 1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    int q; cin >> q;
    while (q--) {
        int op, x1, y1, x2, y2;
        cin >> op >> x1 >> y1 >> x2 >> y2;
        if (op == 1) insert(x1, y1, x2, y2);
        else cout << get_solve(x1, y1, x2, y2) << endl;
    }
    
    return 0;
}