二维莫队解题报告

我写的莫队教程

其实这是一道bzoj上的题(bzoj2639,貌似是权限题,反正我看不了),在YALI做模拟赛的时候遇到了.

然后在网上查到了几篇关于这道题的博客,都和我的做法略有不同…

题目大意

给你一个 $r*c$ 的矩阵,每个点有一个颜色, $m$ 个询问,每次询问一个子矩阵内,每种颜色出现次数的平方和。

$r,c\le 200,m\le 100000$

做法简述

首先我们要明白,莫队究竟在干什么。

莫队其实就是几个指针在那跳来跳去,每跳一步都需要一定的时间,通过对询问排序使得指针跳的总次数尽量小。

所以,这题中询问为 $(x_1,y_1,x_2,y_2)$ ,也就是四个指针在那跳,分别分块再排序就可以了,即:

1
2
3
4
5
6
7
8
9
//为避免和cmath库中的y0y1重名,下文中代码内的x1,y1,x2,y2都用x,y,xx,yy代替
struct Query
{
int x,y,xx,yy,id;
bool operator<(Query& b)
{
return x/B==b.x/B?(y/B==b.y/B?(xx/B==b.xx/B?yy<b.yy:xx<b.xx):y<b.y):x<b.x; //B为分块大小
}
} q[M];

答案更新

一般的莫队都是 $O(1)$ 更新答案的,然而这题是 $O(n)$ (用 $n$ 代表 $r,c$ ) 更新。

移动指针的时候,把一排一起修改。

需要注意的是,8个while的顺序如果排列不当在某些情况下会导致答案出错,所以最好是将所有add都放在del前面(实际上有多种排列顺序都可以在不进行“反操作”的情况下保证答案正确,所有add放在del前面只是其中一种),或者是对“反区间”进行“反操作”。

所谓“反区间”,如:修改 $x_1$ 指针时,本应进行add操作,而此时$y_1>y_2+1$,那么就要将 $(y_2,y_1)$ 这个开区间内的所有点进行del。

while的排列顺序得当可以使“反区间”不可能出现。

“反操作”参考代码:

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
while (x<q[i].x)
{
for (j=y;j<=yy;++j)
{
del(a[x][j]);
}
for (j=yy+1;j<y;++j)
{
add(a[x][j]);
}
++x;
}
while (y<q[i].y)
{
for (j=x;j<=xx;++j)
{
del(a[j][y]);
}
for (j=xx+1;j<x;++j)
{
add(a[j][y]);
}
++y;
}
while (xx>q[i].xx)
{
for (j=y;j<=yy;++j)
{
del(a[xx][j]);
}
for (j=yy+1;j<y;++j)
{
add(a[xx][j]);
}
--xx;
}
while (yy>q[i].yy)
{
for (j=x;j<=xx;++j)
{
del(a[j][yy]);
}
for (j=xx+1;j<x;++j)
{
add(a[j][yy]);
}
--yy;
}
while (x>q[i].x)
{
--x;
for (j=y;j<=yy;++j)
{
add(a[x][j]);
}
for (j=yy+1;j<y;++j)
{
del(a[x][j]);
}
}
while (y>q[i].y)
{
--y;
for (j=x;j<=xx;++j)
{
add(a[j][y]);
}
for (j=xx+1;j<x;++j)
{
del(a[j][y]);
}
}
while (xx<q[i].xx)
{
++xx;
for (j=y;j<=yy;++j)
{
add(a[xx][j]);
}
for (j=yy+1;j<y;++j)
{
del(a[xx][j]);
}
}
while (yy<q[i].yy)
{
++yy;
for (j=x;j<=xx;++j)
{
add(a[j][yy]);
}
for (j=xx+1;j<x;++j)
{
del(a[j][yy]);
}
}
out[q[i].id]=ans;

分块大小

具体计算清楚非常复杂,这里只是估算一下.

$x_1$ 指针的移动次数为 $O(mB)$,$y_2$ 指针的移动次数渐进复杂度中含有 $O\left(\frac{n^4}{B^3}\right)$,取 $mB=\frac{n^4}{B^3}$,得到 $B=nm^{-\frac{1}{4}}$

总时间复杂度为 $O(mlogm+n^2m^{\frac{3}{4}})$

反正这样的分块大小实测比 $\sqrt{n}$ 优秀…有兴趣的话可以严谨地算一算(如果发现我这个估算有问题可以直接在这篇博客下评论)

初始子矩阵

任意一个空矩阵就可以了,如 $x_1=y_1=1,x_2=y_2=0$

参考代码

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
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int N=210;
const int M=100010;

void add(int x);
void del(int x);

int r,c,m,B,a[N][N],lsh[N*N],tot,cnt[N*N],ans,out[M];

struct Query
{
int x,y,xx,yy,id;
bool operator<(Query& b)
{
return x/B==b.x/B?(y/B==b.y/B?(xx/B==b.xx/B?yy<b.yy:xx<b.xx):y<b.y):x<b.x;
}
} q[M];

int main()
{
int i,j,x=1,y=1,xx=0,yy=0;

cin>>r>>c>>m;

B=pow(r*c,0.5)/pow(m,0.25)+1.0;

for (i=1;i<=r;++i)
{
for (j=1;j<=c;++j)
{
cin>>a[i][j];
lsh[tot++]=a[i][j]; //这题要离散化
}
}

sort(lsh,lsh+tot);
tot=unique(lsh,lsh+tot)-lsh;

for (i=1;i<=r;++i)
{
for (j=1;j<=c;++j)
{
a[i][j]=lower_bound(lsh,lsh+tot,a[i][j])-lsh;
}
}

for (i=0;i<m;++i)
{
cin>>q[i].x>>q[i].y>>q[i].xx>>q[i].yy;
q[i].id=i;
}

sort(q,q+m);

for (i=0;i<m;++i)
{
while (x>q[i].x)
{
--x;
for (j=y;j<=yy;++j)
{
add(a[x][j]);
}
}
while (xx<q[i].xx)
{
++xx;
for (j=y;j<=yy;++j)
{
add(a[xx][j]);
}
}
while (y>q[i].y)
{
--y;
for (j=x;j<=xx;++j)
{
add(a[j][y]);
}
}
while (yy<q[i].yy)
{
++yy;
for (j=x;j<=xx;++j)
{
add(a[j][yy]);
}
}
while (x<q[i].x)
{
for (j=y;j<=yy;++j)
{
del(a[x][j]);
}
++x;
}
while (xx>q[i].xx)
{
for (j=y;j<=yy;++j)
{
del(a[xx][j]);
}
--xx;
}
while (y<q[i].y)
{
for (j=x;j<=xx;++j)
{
del(a[j][y]);
}
++y;
}
while (yy>q[i].yy)
{
for (j=x;j<=xx;++j)
{
del(a[j][yy]);
}
--yy;
}
out[q[i].id]=ans;
}

for (i=0;i<m;++i)
{
cout<<out[i]<<endl;
}

return 0;
}

void add(int x)
{
ans=ans+2*cnt[x]+1;
++cnt[x];
}

void del(int x)
{
ans=ans-2*cnt[x]+1;
--cnt[x];
}