A92145.「CodePlus 2018 3 月赛」寻找车位

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

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

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

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

从标准输入读入数据。

第一行包含三个正整数 $n$、$m$、$q$，表示停车场的大小和事件的个数；

接下来 $n$ 行，每行 $m$ 个 0 或 1 的数，如果第 $i$ 行第 $j$ 的数为 $1$，则表示第 $i$ 行第 $j$ 列的车位为空，否则表示这个车位非空；

接下来 $q$ 行，每行表示一个事件，有以下两种形式：

• $0$ $x$ $y$ ：第 $x$ 行第 $y$ 列的车位的停车情况改变，即若此事件发生前这个车位为空，则此事件后这个车位非空，否则此事件后这个车位为空，保证 $1\le x\le n$，$1\le y\le m$
• $1$ $l$ $s$ $r$ $t$：询问以 $(l, s)$ 和 $(r,t)$ 为对角的矩形区域中，最大的全空正方形区域的边长，保证 $1\le l\le r\le n$，$1\le s\le t\le m$

输出到标准输出。

对每个询问输出一行一个整数，表示该询问的全空正方形的边长。

子任务编号	$n,m$ 的额外限制	$q$ 的额外限制	修改操作	是否保证 $s=1,t=m$
1	$n,m\le 500$	$q\le 500$	存在	否
2	$m\le 10$	无	保证不存在	是
3	$m\le 10$	无	存在	是
4	$n\le 40000$	无	保证不存在	是
5	$n\le 40000$	无	存在	是
6	$m\le 10$	无	保证不存在	否
7	$m\le 10$	无	存在	否
8	$n\le 40000$	无	保证不存在	否
9	$n\le 40000$	无	存在	否
10	无	无	存在	否

所有子任务的分值均等分布。

对于所有数据，保证 $n\times m\le 4 \times 10^{6}$，$q\le 2,000$。

---

来自 CodePlus 2018 3 月赛，清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。
Credit：idea/陈俊锟　命题/陈俊锟　验题/吕欣
Git Repo：https://git.thusaac.org/publish/CodePlus3 （链接已失效）
感谢腾讯公司对此次比赛的支持。