| 问题描述 |
|---|
给你一个 $$n*m$$ 的二维矩阵，有 $$q$$ 次查询,每次查询给定一对 $$x,y$$ ，求以 $$x,y$$ 为左上角的最大矩形和。 例如给你一个 $$3*3$$ 的二维矩阵：$$\begin{bmatrix}0&1&1\\1&1&0\\-1&0&-1\\\end{bmatrix}$$ 如果以 $$(1,1)$$ 作为左上角，那么能够构成最大矩形和的右下角是 $$(2,3)$$，和为 $$4$$ 。 |
| 输入描述 |
第一行先是两个正整数 $$n,m$$ 表示二维矩阵的行数和列数。$$(n*m \le 1e5)$$ 接下去 $$n$$ 行，每行 $$m$$ 个实数 $$v$$ 表示值。$$(-1e5 \le v \le 1e5)$$ 接着是一个正整数 $$q$$ 表示查询次数 $$(q \le 1e5)$$ 然后 $$q$$ 行，每行有两个值 $$x,y$$ ，表示以第 $$x$$ 行，第 $$y$$ 列作为左上角。$$(1 \le x \le n,1 \le y \le m)$$
|
| 输出描述 |
针对每次查询，输出以 $$x,y$$ 为左上角的最大矩形和。 |
| 样例输入复制样例 |
3 3 0 1 1 1 1 0 -1 0 -1 2 1 1 3 1 |
| 样例输出 |
4 -1 |
| 相关 |