P4259 [Code+#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$|^|^|存在|^| |$4$|$n \le 400000$|^|保证不存在|^| |$5$|^|^|存在|^| |$6$|$m \le 10$|^|保证不存在|否| |$7$|^|^|存在|^| |$8$|$n \le 400000$|^|保证不存在|^| |$9$|^|^|存在|^| |$10$|无|^|^|^| 所有子任务的分值均等分布。 对于所有数据，保证 $n\times m\le4\times 10^6$，$q\le 2000$。 Credit：https://www.luogu.org/discuss/show?postid=35727