#P3908. 区间最大

区间最大

Description

给出一个n行m列的二维网格a[1...n][1...m],从上往下,行的编号从1至n,从左往右,列的编号是1至m,第i行第j列的数是a[i][j]。
有一个高度是r,宽度是s的长方形计算器。
每次你可以选择二维网格的某个格子(i,j)作为左上角,然后把计算器的左上角对准格子(i,j),覆盖下去,
计算器会自动计算出二维网格被覆盖区域的最大值,注意计算器的边要与二维网格的边平行,同时计算器不能超出二维网格。
二维网格被计算器覆盖的部分,称为二维网格的“子网格”。
现在的任务是:把计算器从二维网格的第1行第1列开始,从上往下,从左往右,每覆盖一次,就输出对应的“子网格”的最大值。


Input Format

第一行,n和m, 1<=n,m<=4000。
接下来是n行m列的二维网格,其中-10000<=a[i][j]<=10000。
最后一行是r和s。1<=r<=n, 1<=s<=m。 

Output Format

共n-r+1行,每行输出m-s+1个数。
其中第i行第j列的数表示把计算器左上角对准二维网格第i行第j列格子,覆盖下去,计算器得到的最大值。

3 3
1 1 2
2 3 4
4 3 2
2 1
2 3 4
4 3 4

Source

单调队列