F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister
Problem 4965. -- 方

4965: 方

Time Limit: 60 Sec  Memory Limit: 512 MB
Submit: 37  Solved: 0
[Submit][Status][Discuss]

Description

天猫有一个停车场,这个停车场是由一个N行M列的网格构成的,每个网格是一个车位。刚开始,某些车位已经停了
车。停车场经常有车辆进进出出。在天猫观察的这一段时间内,总共有Q次车辆进出。在其中的第i次,在第Xi行第
Yi列的车位的停车情况发生了变化,即要么这个车位之前是空的,一辆新的车停了进来,要么是原本停在这个这个
位置的车离开了(是哪一种取决于这个事件之前这个车位有没有停车)。有时,天猫需要在某个连续子矩形区域内
,找一块最大的K行K列的正方形连续网格,使得这块区域中的车位都没有停车。请你在他的每次询问的时候,帮他
找出最大的K值。

Input

第一行N,M,Q,C.Q为操作(停车情况变化或询问)的次数,C为数据类型。
接下来N行,每行M个0或1,描述所有车位的停车情况。
如果第i行第j列的网格没有停车,则这一个数字将会是1,否则是0。
接下来Q行,每行2种情况:
0 x y:第x行第y列的车位的停车情况发生了变化;
1 x1 y1 x2 y2:询问以(x1,y1)和(x2,y2)为对角线的子矩形中,最大的K是多少。
对于所有数据,保证N*M<=4000000,Q<=2000并且N>M
对于情况0,保证1<=X<=N,1<=Y<=M
对于情况1,保证1<=X1<=X2<=N,1<=Y1<=Y2<=M

Output

输出Q行,表示每次变动后最大的K。

Sample Input

http://www.lydsy.com/JudgeOnline/upload/s11.in

Sample Output

http://www.lydsy.com/JudgeOnline/upload/s11.out

HINT

 数据似乎有误,现给出数据,有心人可以查下错www.lydsy.com/JudgeOnline/upload/4965.rar

Source

[Submit][Status][Discuss]

HOME Back