题目描述

access_globe 有一个巨大的停车场,这个停车场有行,每行有个车位。为了美观,access_globe 在建立这个停车场时,规定这个停车场必须是长条形的,即。每个车位都是一个正方形的区域。

最近,access_globe 正在为抽不到 Missing Poster 而苦恼,因此他请你帮他维护这个停车场。你需要支持两个事件:

  • 一辆车停到某一个车位中,或一辆车从某个车位开走
  • 查询一个矩形区域内最大的只包含空车位的正方形区域

如果你能帮 access_globe 高效地解决这个问题,access_globe 一定会好好奖励你的。

题解

线段树神题

这一维开一棵线段树,然后线段树上的每个节点维护3个数组:lm[M], rm[M], val[M]

假设线段树的某个节点表示的是这段区间 () ,那么这个节点的 lm[i] 表示第列中,从第个车位开始往后数有多少个连续的rm[i] 表示从第个车位往前数有多少个连续的`$1$

这个节点的 val[i] 表示如果以第列作为正方形的右边界,且正方形的上下边界在内 (这里的实际上是竖着的一段区间) ,全1的正方形的边长最大是多少

lm[M]rm[M] 都很容易通过左右儿子的值求出来,如何求出 val[M] ?

假设,先考虑这个正方形的上下边界都在或者都在`$[mid+1,r]$

显然此时 val[i] 等于左右儿子的 val[i] 的较大值

如果正方形跨过了呢?

假设我们现在已经知道了正方形的上下边界在内,如果正方形的右边界在,左边界在(即边长为) ,如何判断是否存在合法的正方形?

如图 我们对于中的每一列,找到从第行开始有多少个向上延申的连续的(蓝线),同理找到向下延申的,然后分别找到向上和向下最少的 (绿线) , 记为,如果,就表示一定存在合法的正方形

容易发现如果以为右边界可以构成的最大全1正方形的左边界在,那么以为右边界可以构成的最大全1正方形的左边界不可能小于

所以这个每次查询区间的最小值可以使用单调队列来维护,枚举右端点并且维护另外一个指针,如果此时大于上下两个最小值之和,那就说明不满足条件,继续右移,找到第一个满足条件的,那么这个线段树节点的 val[i] 就等于

这样就通过合并左右儿子两个区间算出了当前节点的值了

注意这样 pushup 一次的复杂度是的,所以进行一次修改或查询

那么怎么查询答案呢?

假设询问是,将在线段树上分为个区间,然后在线段树上合并这些区间即可

一种比较聪明的做法是用一个没有用的节点暂时储存一下这个区间合并得到的答案,最后只需要找出这个临时节点 val[y1]val[y2] 之间的最大值即可

代码

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
#include <bits/stdc++.h>
#define N 4000005
using namespace std;

template <typename T>
inline void read(T &num) {
T x = 0, f = 1; char ch = getchar();
for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') f = -1;
for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ '0');
num = x * f;
}

int n, m, Q;
int len[N<<2], q1[N], q2[N];
vector<int> A[N];
int lm[N<<2], rm[N<<2], val[N<<2];

inline int o(int x, int y) { return x*m+y; }

inline void merge(int ind, int ls, int rs) {
int h1 = 1, h2 = 1, t1 = 0, t2 = 0;
for (int r = 1, l = 1; r <= m; r++) {
while (h1 <= t1 && rm[o(ls,q1[t1])] > rm[o(ls,r)]) t1--;
q1[++t1] = r;
while (h2 <= t2 && lm[o(rs,q2[t2])] > lm[o(rs,r)]) t2--;
q2[++t2] = r;
while (h1 <= t1 && h2 <= t2 && rm[o(ls,q1[h1])] + lm[o(rs,q2[h2])] < r-l+1) {
if (q1[h1] == l) h1++;
if (q2[h2] == l) h2++;
l++;
}
val[o(ind,r)] = max(max(val[o(ls,r)], val[o(rs,r)]), r-l+1);
}
for (int i = 1; i <= m; i++) lm[o(ind,i)] = lm[o(ls,i)] + (lm[o(ls,i)]==len[ls]?lm[o(rs,i)]:0);
for (int i = 1; i <= m; i++) rm[o(ind,i)] = rm[o(rs,i)] + (rm[o(rs,i)]==len[rs]?rm[o(ls,i)]:0);
}
void build(int ind, int l, int r) {
len[ind] = r-l+1;
if (l == r) {
for (int i = 1; i <= m; i++) lm[o(ind,i)] = rm[o(ind,i)] = val[o(ind,i)] = A[l][i];
return;
}
int mid = (l + r) >> 1;
build(ind<<1, l, mid); build(ind<<1|1, mid+1, r);
merge(ind, ind<<1, ind<<1|1);
}
void update(int ind, int l, int r, int x, int y, int v) {
if (l == r) {
lm[o(ind,y)] = rm[o(ind,y)] = val[o(ind,y)] = v;
return;
}
int mid = (l + r) >> 1;
if (x <= mid) update(ind<<1, l, mid, x, y, v);
else update(ind<<1|1, mid+1, r, x, y, v);
merge(ind, ind<<1, ind<<1|1);
}

void query(int ind, int l, int r, int x, int y) {
int ret = 0;
if (x <= l && r <= y) {
merge(0, 0, ind); //用0号点暂时储存答案
return;
}
int mid = (l + r) >> 1;
if (x <= mid) query(ind<<1, l, mid, x, y);
if (mid < y) query(ind<<1|1, mid+1, r, x, y);
}

int main() {
read(n); read(m); read(Q);
for (int i = 1; i <= n; i++) A[i].resize(m+1);
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) {
read(A[i][j]);
}
build(1, 1, n);
for (int i = 1, tp, x, y, a, b; i <= Q; i++) {
read(tp);
if (tp == 0) {
read(x); read(y);
if (A[x][y]) update(1, 1, n, x, y, 0);
else update(1, 1, n, x, y, 1);
A[x][y] = 1 - A[x][y];
} else {
read(x); read(y); read(a); read(b);
for (int j = 1; j <= m; j++) {
lm[o(0,j)] = rm[o(0,j)] = val[o(0,j)] = 0; //用0号点暂时储存答案
}
query(1, 1, n, x, a);
int ans = 0;
for (int j = y; j <= b; j++) {
ans = max(ans, min(j-y+1, val[o(0, j)]));
}
printf("%d\n", ans);
}
}
return 0;
}

评论