算法1

答案矩阵所在位置一定在查询点的下侧，上侧，左侧和右侧
我们先预处理出每一行上下，每一列左右的最大值，这样查询的时候只要找最大的那个就可以了
预处理的方法是单调栈(来源于152、131，不会可以先写这两题)，复杂度$O(nm)$

时间复杂度 $O(4nm+Q)$

C++ 代码

#include<iostream>
#include<cstring>
using namespace std;
const int N = 2010;
char G[N][N];
int n, m;
int U[N], D[N], L[N], R[N];//预处理上下左右，只保留最大值即可
int h[N];//栈
int l[N];//单调栈左侧第一个比当前i小的位置的下标
int pre[N][N];//预处理当前这排每一个直方图的高度
void init()//初始化
{
    //第一个是上侧的，下面四个类似
    for (int i = 1; i <= n;i++)
    {
        for (int j = 1; j <= m;j++)
        {
            if(G[i][j]=='1')
                pre[i][j] = pre[i - 1][j] + 1;
        }
        //单调栈
        pre[i][0] = pre[i][m + 1] = -1;
        h[0] = 0;
        int tt = 0;
        for (int j = 1; j <= m;j++)
        {
            while(pre[i][h[tt]]>=pre[i][j])
                tt--;
            l[j] = h[tt];
            h[++tt] = j;
        }
        h[0] = m + 1;
        tt = 0;
        U[i] = U[i - 1];
        for (int j = m; j >= 1;j--)
        {
            while(pre[i][h[tt]]>=pre[i][j])
                tt--;
            int r = h[tt];
            h[++tt] = j;
            U[i] = max(U[i], (r - l[j] - 1) * pre[i][j]);
        }
    }

    memset(pre, 0, sizeof(pre));
    for (int i = n; i >= 1;i--)
    {
        for (int j = 1; j <= m;j++)
        {
            if(G[i][j]=='1')
                pre[i][j] = pre[i + 1][j] + 1;
        }
        pre[i][0] = pre[i][m + 1] = -1;
        h[0] = 0;
        int tt = 0;
        for (int j = 1; j <= m;j++)
        {
            while(pre[i][h[tt]]>=pre[i][j])
                tt--;
            l[j] = h[tt];
            h[++tt] = j;
        }
        h[0] = m + 1;
        tt = 0;
        D[i] = D[i + 1];
        for (int j = m; j >= 1;j--)
        {
            while(pre[i][h[tt]]>=pre[i][j])
                tt--;
            int r = h[tt];
            h[++tt] = j;
            D[i] = max(D[i], (r - l[j] - 1) * pre[i][j]);
        }
    }

    memset(pre, 0, sizeof(pre));
    for (int i = 1; i <= m;i++)
    {
        for (int j = 1; j <= n;j++)
        {
            if(G[j][i]=='1')
                pre[j][i] = pre[j][i-1] + 1;
        }
        pre[0][i] = pre[n+1][i] = -1;
        h[0] = 0;
        int tt = 0;
        for (int j = 1; j <= n;j++)
        {
            while(pre[h[tt]][i]>=pre[j][i])
                tt--;
            l[j] = h[tt];
            h[++tt] = j;
        }
        h[0] = n + 1;
        tt = 0;
        L[i] = L[i - 1];
        for (int j = n; j >= 1;j--)
        {
            while(pre[h[tt]][i]>=pre[j][i])
                tt--;
            int r = h[tt];
            h[++tt] = j;
            L[i] = max(L[i], (r - l[j] - 1) * pre[j][i]);
        }
    }
    memset(pre, 0, sizeof(pre));
    for (int i = m; i >= 1;i--)
    {
        for (int j = 1; j <= n;j++)
        {
            if(G[j][i]=='1')
                pre[j][i] = pre[j][i+1] + 1;
        }
        pre[0][i] = pre[n+1][i] = -1;
        h[0] = 0;
        int tt = 0;
        for (int j = 1; j <= n;j++)
        {
            while(pre[h[tt]][i]>=pre[j][i])
                tt--;
            l[j] = h[tt];
            h[++tt] = j;
        }
        h[0] = n + 1;
        tt = 0;
        R[i] = R[i + 1];
        for (int j = n; j >= 1;j--)
        {
            while(pre[h[tt]][i]>=pre[j][i])
                tt--;
            int r = h[tt];
            h[++tt] = j;
            R[i] = max(R[i], (r - l[j] - 1) * pre[j][i]);
        }
    }
}
int  main()
{
    cin >> n >> m;
    for (int i = 1; i <= n;i++)
        scanf("%s", G[i] + 1);
    init();
    int t;
    cin >> t;
    while(t--)
    {
        int x, y;
        scanf("%d%d",&x,&y);
        x++;
        y++;
        int res = max(max(U[x - 1], D[x + 1]),max( L[y - 1],R[y+1]));
        printf("%d\n",res);
    }
}