← 返回题目
题库练习 「CodePlus 2018 3 月赛」寻找车位
← 上一题 下一题 →

A6449 | 「CodePlus 2018 3 月赛」寻找车位

时间限制2s
内存限制1024MB
通过 / 提交0/0

题目描述

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$

输出格式

输出到标准输出。

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

输入输出样例

输入 #1
5 4 10
1 1 1 0
1 1 1 1
1 1 0 1
1 0 1 0
1 1 0 0
1 1 1 5 4
1 3 1 3 1
1 3 3 3 3
1 2 3 5 3
0 2 2
1 1 4 2 4
1 1 3 3 3
0 5 1
1 2 3 2 4
1 1 2 2 4
输出 #1
2
1
0
1
1
1
1
1
C++ 编辑器
输入
输出