「QFOI R1」头

GitHub跳转原题关系图返回列表

一个格子的最终颜色由覆盖它的最后一个 t=1 操作决定，没有 t=1 时由第一个操作决定；按行和列分别用并查集求出每个操作负责的格子数，再前缀累加即可。

OJ: luogu

题目 ID: P9715

难度:普及+/提高-

标签:思维离线并查集计数网格

创建: 2026-10-02 15:23

更新: 2026-10-07 12:15

前置题目

luogu P8686[蓝桥杯 2019 省 A] 修改数组B 的 sweep_last / sweep_first 直接复用 A 教的后继并查集（代码 nxtR[x]=x+1 后 find 跳下一个），把「已占用就跳到下一个可用位置」从单序列找最小值改造成行列上求最后一次 t=1 与第一次 t=0，再叠加前缀累加计数。

形式化题目

有一个 $n$ 行 $m$ 列的网格，初始时所有格子都没有颜色。有 $k$ 种颜色，编号 $1\sim k$ 。给出 $q$ 个操作，每个操作用 $(op,l,r,c,t)$ 描述：

若 $op=1$ ，则把第 $l\sim r$ 行的所有格子涂成颜色 $c$ ；
若 $op=2$ ，则把第 $l\sim r$ 列的所有格子涂成颜色 $c$ ；
若 $t=0$ ，则涂色时跳过已经被染色的格子；
若 $t=1$ ，则涂色时用新颜色覆盖已经染色的格子。

求全部操作结束后，每种颜色各覆盖了多少个格子。

暴力解法

思路

最直接的做法就是把网格真的开出来：用 grid[i][j] 记录第 $i$ 行第 $j$ 列当前的颜色， $0$ 表示还没被涂过。然后按输入顺序处理每个操作：

$op=1$ 时枚举第 $l\sim r$ 行的每一列， $op=2$ 时枚举第 $l\sim r$ 列的每一行；
对每个格子判断： $t=1$ 就直接覆盖成 $c$ ； $t=0$ 时只有 grid[i][j] == 0 才涂成 $c$ 。

全部操作做完以后再扫一遍网格，用桶统计每种颜色的格子数。因为每个操作都是老老实实逐格处理，题意里 $t=0$ 和 $t=1$ 的区别被完整保留下来，所以结果一定正确。

代码

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-02 15:23
 * update_at: 2026-10-03 12:16
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
// 直接开一张 n*m 的网格，按题意逐格模拟每一次涂色，最后统计每种颜色的格子数。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 105;       // 暴力只服务小数据：网格每维不超过 100
const int MAXC = 2005;      // 颜色数上限

int n, m, k, q;
int grid[MAXN][MAXN];       // grid[i][j] = 0 表示还没被涂色，否则存颜色编号
ll cnt[MAXC];               // cnt[c]：颜色 c 的格子数

int main() {
    scanf("%d %d %d %d", &n, &m, &k, &q);

    for (int qi = 1; qi <= q; qi++) {
        int op, l, r, c, t;
        scanf("%d %d %d %d %d", &op, &l, &r, &c, &t);

        if (op == 1) {
            // 涂第 l..r 行的所有格子
            for (int i = l; i <= r; i++) {
                for (int j = 1; j <= m; j++) {
                    // t=1 直接覆盖；t=0 只涂还没被涂过的格子
                    if (t == 1 || grid[i][j] == 0) grid[i][j] = c;
                }
            }
        } else {
            // 涂第 l..r 列的所有格子
            for (int i = 1; i <= n; i++) {
                for (int j = l; j <= r; j++) {
                    if (t == 1 || grid[i][j] == 0) grid[i][j] = c;
                }
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (grid[i][j] != 0) cnt[grid[i][j]]++;
        }
    }

    for (int c = 1; c <= k; c++) {
        printf("%lld", cnt[c]);
        putchar(c == k ? '\n' : ' ');
    }
    return 0;
}

复杂度

处理一个操作最多要访问 $\max(n,m)$ 个格子，总时间复杂度 $O(q\cdot\max(n,m))$ ；空间复杂度 $O(nm)$ （网格本身）。

瓶颈

这个做法有两处硬伤：

空间上， $n=m=2\times10^6$ 时网格有 $4\times10^{12}$ 个格子，根本开不出来；
时间上，哪怕 $q=1$ ，一次涂一整行 / 一整列也要访问 $2\times10^6$ 个格子。

瓶颈来自"把网格逐格存下来"这个建模方式。观察题目可以发现：同一行里的所有格子，经历的涂行操作完全相同；同一列里的所有格子，经历的涂列操作也完全相同。 一个格子的命运只由它所在的行和它所在的列共同决定，因此完全不必逐格处理，只要分别算出每一行、每一列上的关键操作，再组合计数即可。

正解

思路

第一步：一个格子的最终颜色

设所有覆盖格子 $(x,y)$ 的操作中，最后一个 $t=1$ 的操作是第 $p$ 个操作。

若存在这样的 $p$ ：第 $p$ 个操作把 $(x,y)$ 涂成它的颜色。在它之后的任何覆盖 $(x,y)$ 的操作都只能是 $t=0$ （否则会与" $p$ 是最后一个 $t=1$ "矛盾），而 $t=0$ 遇到已染色的格子直接跳过，不会改动颜色。所以 $(x,y)$ 的最终颜色就是第 $p$ 个操作的颜色：格子颜色 = 覆盖它的最后一个 $t=1$ 操作的颜色。
若不存在这样的 $p$ ：所有覆盖 $(x,y)$ 的操作都是 $t=0$ 。那么第一个覆盖 $(x,y)$ 的操作给它上了色，后面每个操作都因为"已染色"而跳过。所以格子颜色 = 第一个覆盖它的操作的颜色。

于是每个格子只关心两件事：它所在的行 / 列有没有被 $t=1$ 的操作覆盖过，以及如果从来没有过，谁是第一个覆盖它的操作。

第二步：把行和列分成两类

对每一行 $x$ ，定义 lastRow1[x] 为覆盖第 $x$ 行的、编号最大的 $t=1$ 操作（没有就是 $0$ ）；对每一列 $y$ 同理定义 lastCol1[y]。

把所有格子按下面两条规则分类：

第一类：lastRow1[x] > 0 或 lastCol1[y] > 0。这类格子的颜色由覆盖它的最后一个 $t=1$ 操作决定，其编号就是 lastRow1[x] 与 lastCol1[y] 中较大的那个。
第二类：lastRow1[x] == 0 且 lastCol1[y] == 0。这类格子从头到尾只被 $t=0$ 操作覆盖，颜色由第一个覆盖它的操作决定。

记 $n_0=\#\{x\mid \texttt{lastRow1[x]}=0\}$ ， $m_0=\#\{y\mid \texttt{lastCol1[y]}=0\}$ ，也就是"纯 $t=0$ "的行数和列数。

第三步：每个操作负责多少格子

同一个操作在不同格子上扮演的角色可能是"最后一次 $t=1$ 覆盖"或"第一次涂色"，下面分别统计。

对每个 $t=1$ 的涂行操作 $i$ ，它最终"定调"的格子有两类来源，但都可以归结为：行必须是"lastRow1 恰为 $i$ "的行，列必须是没有被编号 $>i$ 的 $t=1$ 列操作覆盖过的列。前者的行数是 rowLastCnt[i]，后者的列数是

m_0+\sum_{k<i}\texttt{colLastCnt[k]},

这个量随着 $i$ 增大只增不减，可以边扫边维护。对 $t=1$ 的涂列操作对称处理。

对每个 $t=0$ 的涂行操作 $i$ ，它负责的格子必须满足：行是"lastRow1 为 $0$ 且第一个覆盖它的操作恰为 $i$ "的行，列是"lastCol1 为 $0$ 且第一个覆盖它的列操作晚于 $i$ "的列。后者的列数等于 $m_0$ 减去"第一个覆盖它的列操作编号 $<i$ "的列数，记为 $m_0-B$ 。对 $t=0$ 的涂列操作对称处理。

第四步：两次扫描 + 并查集

上面的 lastRow1 / lastCol1 和"第一个覆盖"都要对每个行 / 列只赋值一次，这正好用"下一个未赋值的下标"并查集来做，并额外加一个哨兵 $n+1$ （或 $m+1$ ）：

倒序扫描（求"最后一次 $t=1$ "）： $i$ 从 $q$ 到 $1$ ，遇到 $t=1$ 的操作就把它区间内所有还没被赋值的行（或列）赋成 $i$ ，然后从并查集里删掉。倒着扫，第一次赋值就是最后一个覆盖。
正序扫描（求"第一次 $t=0$ "）： $i$ 从 $1$ 到 $q$ ，遇到 $t=0$ 的操作就把它区间内所有还没被赋值的行（或列）删掉；其中 lastRow1 == 0（对列是 lastCol1 == 0）的那些才计入这个操作。正着扫，第一次赋值就是第一个覆盖。

两个扫描里每个行 / 列都只会被删除一次，配合路径压缩总复杂度是 $O((n+m+q)\alpha)$ 。注意正序扫描时也会删除 lastRow1 > 0 的行——它们属于第一类，不属于第二类，删掉它们不会影响答案，却保证了每个下标只被处理一次。

第五步：正序累加答案

最后再正序扫一遍所有操作，维护四个前缀量：

量	含义
$C$	`lastRow1 < i` 的行数，初始为 $n_0$
$A$	`lastCol1 < i` 的列数，初始为 $m_0$
$D$	第一次涂色操作编号 $<i$ 的纯 $t=0$ 行数
$B$	第一次涂色操作编号 $<i$ 的纯 $t=0$ 列数

对第 $i$ 个操作：

涂行、 $t=1$ ：ans[c] += rowLastCnt[i] * A，然后 $C$ 加上这个块大小；
涂行、 $t=0$ ：ans[c] += rowFirstCnt[i] * (m_0-B)，然后 $D$ 加上这个块大小；
涂列、 $t=1$ ：ans[c] += colLastCnt[i] * C，然后 $A$ 加上这个块大小；
涂列、 $t=0$ ：ans[c] += colFirstCnt[i] * (n_0-D)，然后 $B$ 加上这个块大小。

每种颜色最多被计入 $n\cdot m=4\times10^{12}$ 个格子，所以答案要开 long long。

样例 1 的完整推演

样例 1 的四个操作是：

编号	操作	颜色	$t$
1	涂行 $[2,4]$	1	0
2	涂列 $[4,5]$	1	1
3	涂列 $[2,4]$	2	0
4	涂行 $[1,1]$	2	1

倒序扫描：只有操作 4 和 2 是 $t=1$ ，得到 lastRow1[1] = 4（行 1），lastCol1[4] = lastCol1[5] = 2（列 4、5）。于是 $n_0=4$ （行 2、3、4、5）， $m_0=3$ （列 1、2、3）。

正序扫描 $t=0$ 的操作：操作 1 覆盖行 2、3、4，它们 lastRow1 都是 $0$ ，都计入，块大小 $3$ ；操作 3 覆盖列 2、3、4，但列 4 的 lastCol1 非 $0$ ，只有列 2、3 计入，块大小 $2$ 。

累加过程：

$i$	操作	块大小	使用的量	贡献	累加后
1	行 $t=0$ ，颜色 1	3	$m_0-B=3-0$	$3\times3=9$	$D=3$
2	列 $t=1$ ，颜色 1	2	$C=4$	$2\times4=8$	$A=3+2=5$
3	列 $t=0$ ，颜色 2	2	$n_0-D=4-3$	$2\times1=2$	$B=2$
4	行 $t=1$ ，颜色 2	1	$A=5$	$1\times5=5$	$C=5$

颜色 1 得到 $9+8=17$ ，颜色 2 得到 $2+5=7$ ，与样例输出 17 7 一致。第 2 行里 $C=4$ 表示"lastRow1 为 $0$ 的行"有 4 行，它们全部落在操作 4 的行 1 之外——所以操作 2 涂的列 4、5 在这 4 行上的 $8$ 个格子都由它定调。

代码

sweep_last() 倒序确定每个 $t=1$ 操作负责的行 / 列，sweep_first() 正序确定每个 $t=0$ 操作负责的行 / 列，calc_answer() 正序累加四种贡献。并查集用迭代路径压缩写成 findR / findC，避免递归。

cpp

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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-02 15:23
 * update_at: 2026-10-03 12:16
 */
// P9715 「QFOI R1」头：正解。
// 关键结论：一个格子最后的颜色，等于覆盖它的最后一个 t=1 操作的颜色；
// 如果没有任何 t=1 操作覆盖它，则等于覆盖它的第一个操作（必为 t=0）的颜色。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 2000005;   // 行 / 列下标上限
const int MAXQ = 2000005;   // 操作数上限
const int MAXK = 500005;    // 颜色数上限

int n, m, k, q;             // 行数、列数、颜色数、操作数

int L[MAXQ], R[MAXQ];       // 第 i 个操作的区间 [L[i], R[i]]
int colOf[MAXQ];            // 第 i 个操作使用的颜色
// kind[i]：0 = 涂行且 t=0，1 = 涂行且 t=1，2 = 涂列且 t=0，3 = 涂列且 t=1
unsigned char kind[MAXQ];

int lastRow1[MAXN];         // lastRow1[x]：最后一个整行覆盖第 x 行的 t=1 操作编号，0 表示没有
int lastCol1[MAXN];         // lastCol1[x]：最后一个整列覆盖第 x 列的 t=1 操作编号，0 表示没有

// val[i]：第 i 个操作在这一遍扫描中“新确定”的行数（涂行）或列数（涂列）
int val[MAXQ];

// 并查集：nxtR[x] 指向 >= x 的第一个还没被“确定”的行，nxtC 同理作用在列上
int nxtR[MAXN], nxtC[MAXN];

ll ans[MAXK];               // ans[c]：颜色 c 最终覆盖的格子数

// ---------- 快速读入 ----------
char buf[1 << 16];
int bufPos = 0, bufLen = 0;

inline char getch() {
    if (bufPos == bufLen) {
        bufLen = (int)fread(buf, 1, 1 << 16, stdin);
        bufPos = 0;
        if (bufLen <= 0) return 0;
    }
    return buf[bufPos++];
}

inline int readInt() {
    char ch = getch();
    while (ch < '0' || ch > '9') {
        if (ch == 0) return -1;
        ch = getch();
    }
    int x = 0;
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + (ch - '0');
        ch = getch();
    }
    return x;
}

// 返回 >= x 的第一个还没被确定的行（路径压缩的迭代写法）
int findR(int x) {
    while (nxtR[x] != x) {
        nxtR[x] = nxtR[nxtR[x]];
        x = nxtR[x];
    }
    return x;
}

// 返回 >= x 的第一个还没被确定的列
int findC(int x) {
    while (nxtC[x] != x) {
        nxtC[x] = nxtC[nxtC[x]];
        x = nxtC[x];
    }
    return x;
}

void read_data() {
    n = readInt();
    m = readInt();
    k = readInt();
    q = readInt();
    for (int i = 1; i <= q; i++) {
        int op = readInt();
        L[i] = readInt();
        R[i] = readInt();
        colOf[i] = readInt();
        int t = readInt();
        kind[i] = (unsigned char)((op - 1) * 2 + t);
    }
}

// 倒序扫描：确定每个 t=1 操作是哪些行 / 列的“最后一次覆盖”
void sweep_last() {
    for (int i = 1; i <= n + 1; i++) nxtR[i] = i;
    for (int i = 1; i <= m + 1; i++) nxtC[i] = i;

    for (int i = q; i >= 1; i--) {
        if ((kind[i] & 1) == 0) continue;   // 只处理 t=1
        int l = L[i], r = R[i];
        if (kind[i] <= 1) {                 // 涂行
            int cnt = 0;
            int x = findR(l);
            while (x <= r) {
                lastRow1[x] = i;
                cnt++;
                nxtR[x] = x + 1;            // 这一行已经确定，从并查集里删掉
                x = findR(x + 1);
            }
            val[i] = cnt;
        } else {                            // 涂列
            int cnt = 0;
            int x = findC(l);
            while (x <= r) {
                lastCol1[x] = i;
                cnt++;
                nxtC[x] = x + 1;
                x = findC(x + 1);
            }
            val[i] = cnt;
        }
    }
}

// 正序扫描：确定每个 t=0 操作是哪些行 / 列的“第一次覆盖”
// 只有从未被 t=1 覆盖过的行 / 列，才可能作为“第一次涂色”的来源
void sweep_first() {
    for (int i = 1; i <= n + 1; i++) nxtR[i] = i;
    for (int i = 1; i <= m + 1; i++) nxtC[i] = i;

    for (int i = 1; i <= q; i++) {
        if ((kind[i] & 1) != 0) continue;   // 只处理 t=0
        int l = L[i], r = R[i];
        if (kind[i] <= 1) {                 // 涂行
            int cnt = 0;
            int x = findR(l);
            while (x <= r) {
                if (lastRow1[x] == 0) cnt++;
                nxtR[x] = x + 1;
                x = findR(x + 1);
            }
            val[i] = cnt;
        } else {                            // 涂列
            int cnt = 0;
            int x = findC(l);
            while (x <= r) {
                if (lastCol1[x] == 0) cnt++;
                nxtC[x] = x + 1;
                x = findC(x + 1);
            }
            val[i] = cnt;
        }
    }
}

// 正序累加答案
// C = 当前 lastRow1 < i 的行数；A = 当前 lastCol1 < i 的列数
// D = 当前“第一次覆盖” < i 的纯 t=0 行数；B = 当前“第一次覆盖” < i 的纯 t=0 列数
void calc_answer() {
    ll C = 0, A = 0, D = 0, B = 0;
    for (int i = 1; i <= n; i++) if (lastRow1[i] == 0) C++;   // C 的初值就是 n0
    for (int i = 1; i <= m; i++) if (lastCol1[i] == 0) A++;   // A 的初值就是 m0
    ll n0 = C, m0 = A;

    for (int i = 1; i <= q; i++) {
        int c = colOf[i];
        if (kind[i] <= 1) {                 // 涂行
            if (kind[i] == 1) {             // t=1：这些格子由本操作最后覆盖
                ans[c] += (ll)val[i] * A;
                C += val[i];
            } else {                        // t=0：这些格子是“第一次被涂”
                ans[c] += (ll)val[i] * (m0 - B);
                D += val[i];
            }
        } else {                            // 涂列
            if (kind[i] == 3) {             // t=1
                ans[c] += (ll)val[i] * C;
                A += val[i];
            } else {                        // t=0
                ans[c] += (ll)val[i] * (n0 - D);
                B += val[i];
            }
        }
    }
}

int main() {
    read_data();
    sweep_last();
    sweep_first();
    calc_answer();

    for (int i = 1; i <= k; i++) {
        printf("%lld", ans[i]);
        putchar(i == k ? '\n' : ' ');
    }
    return 0;
}

复杂度

时间 $O\big((n+m+q)\,\alpha(n+m)\big)$ ，其中 $\alpha$ 是并查集的近似反阿克曼函数；空间 $O(n+m+q+k)$ 。

$n=m=q=2\times10^6$ 时，实测约 $0.15$ 秒、 $68$ MB。

总结

这道题的核心是把"逐格涂色"换成"按行、按列记账"，整条链路是：

定位决定者：格子的最终颜色要么来自覆盖它的最后一个 $t=1$ 操作，要么（没有这种操作时）来自覆盖它的第一个 $t=0$ 操作。这一步把"多次涂色的先后博弈"压缩成一个格子只看两个操作的结论。
按行 / 列分组：同一行的格子共享全部涂行操作，同一列的格子共享全部涂列操作。于是"格子有没有 $t=1$ "退化成"行或列有没有 $t=1$ "，二维问题降成一维。
并查集去重：每个行 / 列只需要被"第一次"或"最后一次"赋值一次，用"下一个未赋值下标"的并查集配上哨兵，把两次扫描压到近似线性。
前缀累加：扫描时维护 $C,A,D,B$ 四个前缀量，把"某个操作负责的格子数"写成 块大小 × 前缀量，避免枚举行列配对，也避免开二维数组。

最值得记住的是第 1 步： $t=0$ 的语义是"遇到已染色就跳过"，所以一旦某个格子被 $t=1$ 操作碰过，之后所有 $t=0$ 操作对它都无效；反过来，如果一个格子从头到尾都没被 $t=1$ 碰过，那就只能是"先到先得"。这两句话分别解释了第一个扫描和第二个扫描存在的理由。

P9715 「QFOI R1」头

题目背景

可以看看这个讨论：https://www.luogu.com.cn/discuss/703835。

题目描述

小 R 是一个可爱的女孩子。有一天，她在被摸头时，突然灵光乍现，便随手加强了一道题给你做。

这道题的名字叫涂色游戏。初始时你有一个 $n$ 行 $m$ 列的网格，所有格子上都没有颜色。有 $k$ 种颜色的刷子，颜色编号为 $1\sim k$ 。然后给出 $q$ 次操作，每次操作给出 $op,l,r,c,t$ 五个参数：

如果 $op=1$ ，表示将第 $l\sim r$ 行的所有格子涂成颜色 $c$ 。
如果 $op=2$ ，表示将第 $l\sim r$ 列的所有格子涂成颜色 $c$ 。
如果 $t=0$ ，意味着如果涂色时遇到已经被染色的格子，就不再进行染色。
如果 $t=1$ ，意味着如果涂色时遇到已经被染色的格子，就用新的颜色覆盖它。

在所有涂色操作结束以后，对于每种颜色，求出有多少个格子被染成了这种颜色。

输入格式

第一行四个整数 $n,m,k,q$ ，表示行数、列数、颜色数和操作数。

接下来 $q$ 行，每行五个整数 $op,l,r,c,t$ ，表示这次操作的参数。

输出格式

一行 $k$ 个整数，第 $i$ 个整数表示被染成颜色 $i$ 的格子数量。

输入输出样例 #1

输入 #1

text

输出 #1

text

117 7

输入输出样例 #2

输入 #2

text

输出 #2

text

15 4 16

说明/提示

样例 $1$ 解释

用浅灰色表示颜色 $1$ ，灰色表示颜色 $2$ 。

涂色过程如图所示：

共有 $17$ 个区域被染成颜色 $1$ ， $7$ 个区域被染成颜色 $2$ 。

数据范围

本题共 $20$ 个测试点，每个测试点 $5$ 分。

对于全部数据，保证 $1\le n,m,q\le 2\times 10^6$ ， $1\le k\le 5\times 10^5$ ， $op\in\{1,2\}$ ，若 $op=1$ 则 $1\le l\le r\le n$ ，若 $op=2$ 则 $1\le l\le r\le m$ ， $1\le c\le k$ ， $t\in\{0,1\}$ 。

对于测试点 $1\sim 3$ ：保证 $n,m,k,q\le 200$ 。
对于测试点 $4\sim 6$ ：保证 $n,m,k,q\le 2\times 10^3$ 。
对于测试点 $7\sim 9$ ：保证 $n,m,k,q\le 10^5$ ， $op=1$ 。
对于测试点 $10\sim 12$ ：保证 $n,m,k,q\le 10^5$ ， $t=1$ 。
对于测试点 $13\sim 18$ ：保证 $n,m,k,q\le 10^5$ 。
对于测试点 $19\sim 20$ ：无特殊限制。

「QFOI R1」头

目录

形式化题目

暴力解法

思路

代码

复杂度

瓶颈

正解

思路

第一步：一个格子的最终颜色

第二步：把行和列分成两类

第三步：每个操作负责多少格子

第四步：两次扫描 + 并查集

第五步：正序累加答案

样例 1 的完整推演

代码

复杂度

总结