自动搬运

查看原文

来自洛谷，原作者为

	Wen_kr 谢谢你。

搬运于2025-08-24 21:58:16，当前版本为作者最后更新于2020-05-19 11:22:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

观察到 $m$ 和 $q$ 都比较小，我们可以接受在复杂度里带上 $m$，比如 $O(qm\log n)$。

不妨考虑使用线段树来解决这个问题。

线段树上的一个节点描述的是 $x$ 坐标在 $[l,r]$ 区间内的最大正方形有多大。

因为第二种询问涉及两维，我们在一个节点上维护对于每一个 $y$，右边界落在 $y$ 上的最大正方形有多大，这样我们每个节点都维护了 $m$ 个量，空间复杂度是 $O(4nm)$，可以接受。

考虑怎么合并两个子区间。

容易发现的是，我们只需要考虑跨过 $x=mid$ 这条线的正方形。

考虑这样一个矩阵：

--------------- x = r
0 0 0 0 0 1 1 0
1 0 1 1 0 1 1 0
1 0 0 1 0 0 1 0
1 1 1 1 1 1 1 1
--------------- x = mid
1 1 1 1 1 1 1 1
1 1 1 1 0 1 0 1
0 1 1 1 1 0 1 1
1 0 0 0 1 0 0 1
--------------- x = l

注意到我们只需要从 $x=mid$ 这条线向上向下走连续的 $1$ 长度，其他的 $1$ 都是没用的，先将这些没用的 1 删去。

--------------- x = r
0 0 0 0 0 0 1 0
1 0 0 1 0 0 1 0
1 0 0 1 0 0 1 0
1 1 1 1 1 1 1 1
--------------- x = mid
1 1 1 1 1 1 1 1
1 1 1 1 0 1 0 1
0 1 1 1 0 0 0 1
0 0 0 0 0 0 0 1
--------------- x = l

然后将矩阵变形为长度：

--------------- x = r
3 1 1 3 1 1 4 1
--------------- x = mid
2 3 3 3 1 2 1 4
--------------- x = l

记上半部分的长度数组为 $len1$，下半部分的长度数组为 $len2$。

考虑对于一个 $y=p$ 怎么求得答案：

最粗暴的方法是，我们二分一个左端点 $q$，那么 $[q,p]$ 之间存在合法正方形的条件就是 $\min_{q\leq i\leq p}\{len1_i\}+\min_{q\leq i\leq p}\{len2_i\}\geq p-q+1$。

二分的时间复杂度是不优秀的，但是观察到随着 $y$ 的递增左端点也一定递增，我们就能将这个二分删掉了。

我们只需要知道左端点到当前点之间两个长度数组的最小值，这可以使用单调队列解决。

这样我们就实现了对答案的计算，最后我们只需要计算出 $len1$ 和 $len2$ 数组。

在线段树上维护 $up$ 和 $down$ 表示每个节点对应子区间内从上往下最长的连续 $1$ 长度和从下往上最长的连续 $1$ 长度，这样在合并的时候左儿子的 $down$ 就是我们上半的 $len1$，右儿子的 $up$ 就是我们下半的 $len2$。

$up$ 和 $down$ 的合并较为简单。

具体实现见代码。

#include <bits/stdc++.h>

using namespace std;

int n,m;

struct Node
{
	int val[16000050];
	int* operator [] (int x)
	{
		return val + x * m;
	}
}up,down,ans,M;

int q1[2050],q2[2050];
int head1,head2,tail1,tail2;

inline void Merge(int rt,int ls,int rs,int L,int R)
{
	head1 = 1,head2 = 1;
	tail1 = 0,tail2 = 0;
	for(int i = 1,j = 1;i <= m; ++ i)
	{
		while(head1 <= tail1 && down[ls][i] < down[ls][q1[tail1]]) tail1 --;
		q1[++ tail1] = i;
		while(head2 <= tail2 && up[rs][i] < up[rs][q2[tail2]]) tail2 --;
		q2[++ tail2] = i;
		while(j <= i && i - j + 1 > up[rs][q2[head2]] + down[ls][q1[head1]])
		{
			j ++;
			if(q2[head2] < j) head2 ++;
			if(q1[head1] < j) head1 ++;
		}
		ans[rt][i] = max(ans[ls][i],max(ans[rs][i],i - j + 1));
	}
	for(int i = 1;i <= m; ++ i)
		up[rt][i] = up[ls][i] + (up[ls][i] == L ? up[rs][i] : 0),
		down[rt][i] = down[rs][i] + (down[rs][i] == R ? down[ls][i] : 0);
}

void Build(int rt,int l,int r)
{
	if(l == r)
	{
		for(int i = 1;i <= m; ++ i)
			up[rt][i] = down[rt][i] = ans[rt][i] = M[l][i];
		return ;
	}
	int mid = (l + r) >> 1;
	Build(rt << 1,l,mid);
	Build(rt << 1 | 1,mid + 1,r);
	Merge(rt,rt << 1,rt << 1 | 1,mid - l + 1,r - mid);
}

int pos,y;

void Update(int rt,int l,int r)
{
	if(l == r)
	{
		up[rt][y] = down[rt][y] = ans[rt][y] = (M[pos][y] ^ 1);
		M[pos][y] ^= 1;
		return ;
	}
	int mid = (l + r) >> 1;
	if(mid >= pos) Update(rt << 1,l,mid);
	else Update(rt << 1 | 1,mid + 1,r);
	Merge(rt,rt << 1,rt << 1 | 1,mid - l + 1,r - mid);
}

int ll,rr;

void Query(int rt,int l,int r)
{
	if(ll <= l && r <= rr)
	{
		Merge(0,0,rt,l - ll,r - l + 1);
		return ;
	}
	int mid = (l + r) >> 1;
	if(mid >= ll) Query(rt << 1,l,mid);
	if(mid < rr) Query(rt << 1 | 1,mid + 1,r);
}

template<class T> inline void read(T &x) {
    x = 0; char c = getchar();
    while (!isdigit(c)) c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
}

int main()
{
	int q;
	read(n); read(m); read(q);
	for(int i = 1;i <= n; ++ i)
		for(int j = 1;j <= m; ++ j)
			read(M[i][j]);
	Build(1,1,n);
	for(int i = 1;i <= q; ++ i)
	{
		int op; read(op);
		if(op == 0)
		{
			int x; read(x); read(y);
			pos = x;
			Update(1,1,n);
		}
		else
		{
			int l,s,r,t; read(l); read(s); read(r); read(t);
			ll = l,rr = r;
			for(int i = 1;i <= m; ++ i) up[0][i] = down[0][i] = ans[0][i] = 0;
			Query(1,1,n); int as = 0;
			for(int i = s;i <= t; ++ i) as = max(as,min(ans[0][i],i - s + 1));
			printf("%d\n",as);
		}
	}
	
	return 0;
}