你们怎么都会 $O(HW+Q)$ 的做法啊。
提供一种好想但不一定好写的做法。
官解中有这样一个做法：
1
2
3
4
5
6
7
8
9
10
|
// P[x][y] : マス(x,y)が何回目の操作で上書きされたか（まだ上書きされていないなら0）
for (int i = Q; i >= 1; i--) {
for (int x = R[i]; x >= 1; x--) {
if (P[x][C[i]] != 0) break;
for (int y = C[i]; y >= 1; y--) {
if (P[x][y] != 0) break;
P[x][y] = i;
}
}
}
|
利用倒序处理的单调性，这是显然 $O(HW+Q)$ 的。
但要是考场上想不出来这样优秀的倒着扫描，只会倒序处理呢？
我们维护一个 $g_i$ 表示第 $i$ 行的最后覆盖位置。每次涂色时往后推进 $g_i$。这个做法可能会被想当然地认为是 $O(HW)$ 的，实则不然。
:::error[错误解法]
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
|
#include<bits/stdc++.h>
#define fs first
#define sc second
using namespace std;
pair<pair<int,int>,char> op[200005];
string ans[1000005];
int fg[1000005];
int h,w,q;
int main(){
memset(fg,0xff,sizeof(fg));
cin>>h>>w>>q;
for(int i=1;i<=q;i++){
int r,c;
char x;
cin>>r>>c>>x;
op[i]={{r,c},x};
}
for(int t=q;t>=1;t--){
int r=op[t].fs.fs;
int c=op[t].fs.sc;
char x=op[t].sc;
for(int i=1;i<=r;i++){
for(int j=fg[i]+1;j<c;j++){
fg[i]=j;
ans[i]+=x;
}
}
}
for(int i=1;i<=h;i++){
for(int j=0;j<=fg[i];j++){
putchar(ans[i][j]);
}
for(int j=fg[i]+1;j<w;j++){
putchar('A');
}
putchar('\n');
}
return 0;
}
|
:::
由于我们没有维护竖着的单调性，导致每次内层循环都完整地扫描了 $r$ 行，复杂度达到 $O(QH)$。不能接受。
于是可以想到那个传说中的神秘算法：根号分治。
当 $H$ 大时，我们取 $W$ 作为主维进行扫描；反之亦然。这样做的复杂度将会是 $O(Q \times \min(H,W))$ 的。由于 $\sqrt{H \times W} \le \frac{H+W}{2}$，于是复杂度低于 $O(Q \times \sqrt{H \times W})$。可以通过。
:::success[正确代码]
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
|
#include<bits/stdc++.h>
#define fs first
#define sc second
using namespace std;
pair<pair<int,int>,char> op[200005];
string ans[1000005];
int fg[1000005];
int h,w,q;
int main(){
memset(fg,0xff,sizeof(fg));
cin>>h>>w>>q;
for(int i=1;i<=q;i++){
int r,c;
char x;
cin>>r>>c>>x;
op[i]={{r,c},x};
}
if(h<w){
for(int t=q;t>=1;t--){
int r=op[t].fs.fs;
int c=op[t].fs.sc;
char x=op[t].sc;
for(int i=1;i<=r;i++){
for(int j=fg[i]+1;j<c;j++){
fg[i]=j;
ans[i]+=x;
}
}
}
for(int i=1;i<=h;i++){
for(int j=0;j<=fg[i];j++){
putchar(ans[i][j]);
}
for(int j=fg[i]+1;j<w;j++){
putchar('A');
}
putchar('\n');
}
}else{
for(int t=q;t>=1;t--){
int r=op[t].fs.sc;
int c=op[t].fs.fs;
char x=op[t].sc;
for(int i=1;i<=r;i++){
for(int j=fg[i]+1;j<c;j++){
fg[i]=j;
ans[i]+=x;
}
}
}
for(int i=1;i<=h;i++){
for(int j=1;j<=w;j++){
if(fg[j]>=i-1)putchar(ans[j][i-1]);
else putchar('A');
}
putchar('\n');
}
}
return 0;
}
/*
3 2 3
2 2 B
3 1 C
1 2 D
*/
|
:::