P4259 [Code+#3] Finding Parking Spaces

access_globe has a huge parking lot with $n$ rows and $m$ spaces per row. For aesthetics, when building this parking lot, access_globe stipulated that it must be strip-shaped, i.e., $n\ge m$. Each parking space is a square area. Recently, access_globe has been distressed about not being able to draw "Missing Poster", so he asks you to help maintain this parking lot. You need to support two types of events: - A car parks in a certain space, or a car leaves a certain space. - Query, within a rectangular region, the largest square region consisting only of empty spaces. If you can help access_globe solve this efficiently, access_globe will reward you well.

The first line contains three positive integers $n$, $m$, and $q$, denoting the size of the parking lot and the number of events. The next $n$ lines each contain $m$ numbers, either $0$ or $1$. If the number at row $i$, column $j$ is $1$, then the space at row $i$, column $j$ is empty; otherwise, that space is non-empty. The next $q$ lines each describe an event in one of the following two forms: - $0$ $x$ $y$: The occupancy status of the space at row $x$, column $y$ toggles. That is, if this space was empty before this event, it becomes non-empty after the event; otherwise, it becomes empty. It is guaranteed that $1\le x\le n$, $1\le y\le m$. - $1$ $l$ $s$ $r$ $t$: Query the side length of the largest all-empty square region within the rectangle with opposite corners $(l, s)$ and $(r, t)$. It is guaranteed that $1\le l\le r\le n$, $1\le s\le t\le m$.

For each query, output one integer on its own line, representing the side length of the largest all-empty square for that query.

| Subtask ID | Extra constraints on $n, m$ | Extra constraints on $q$ | Update operations | Whether guaranteed that $s=1, t=m$ | |:-:|:-:|:-:|:-:|:-:| |$1$|$n,m \le 500$|$q \le 500$|Present|No| |$2$|$m \le 10$|None|Guaranteed absent|Yes| |$3$|^|^|Present|^| |$4$|$n \le 400000$|^|Guaranteed absent|^| |$5$|^|^|Present|^| |$6$|$m \le 10$|^|Guaranteed absent|No| |$7$|^|^|Present|^| |$8$|$n \le 400000$|^|Guaranteed absent|^| |$9$|^|^|Present|^| |$10$|None|^|^|^| All subtasks are evenly weighted. For all testdata, it is guaranteed that $n\times m\le 4\times 10^6$, $q\le 2000$. Credit: https://www.luogu.org/discuss/show?postid=35727 Translated by ChatGPT 5