[模板]二维ST表

时间：2024-11-13 09:05:50

考试yy二维ST表失败导致爆零。

其实和一维的ST表很像...

也是设$f[i][j][p][q]$为以$(i, j)$为左上角，长为$2^p$，宽为$2^q$的矩形的最大值。

算法流程是先把每一行都分别求一遍一维的ST表，然后再把行与行之间合并...

查询和一维ST表类似

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

using namespace std;

#define reg register

inline int read() {

    int res=;char ch=getchar();bool fu=;

    while(!isdigit(ch))fu|=(ch=='-'),ch=getchar();

    while(isdigit(ch))res=(res<<)+(res<<)+(ch^),ch=getchar();

    return fu?-res:res;

}

int n, m;

int a[][];

int st[][][][];

inline int query(int x1, int y1, int x2, int y2)

{

    int k1 = log2(x2 - x1 + ), k2 = log2(y2 - y1 + );

    return max(st[x1][y1][k1][k2], max(st[x2-(<<k1)+][y1][k1][k2], max(st[x1][y2-(<<k2)+][k1][k2], st[x2-(<<k1)+][y2-(<<k2)+][k1][k2])));

}

int main()

{

    freopen("yy.in", "r", stdin);

    freopen("yy.out", "w", stdout);

    n = read(), m = read();

    for (reg int i =  ; i <= n ; ++i)

        for (reg int j =  ; j <= m ; ++j)

            st[i][j][][] = a[i][j] = read();

    for (reg int p =  ; p <=  ; p ++)

        for (reg int q =  ; q <=  ; q ++)

            if (p !=  or q != )

                for (reg int i =  ; i + (<<p) -  <= n ; i ++)

                    for (reg int j =  ; j + (<<q) -  <= m ; j ++)

                        if (!p) st[i][j][p][q] = max(st[i][j][p][q - ], st[i][j+(<<(q-))][p][q - ]);

                        else st[i][j][p][q] = max(st[i][j][p-][q], st[i+(<<(p-))][j][p-][q]);

    int q = read();

    while(q--)

    {

        int x1=read(),y1=read(),x2=read(),y2=read();

        printf("%d\n", query(x1,y1,x2,y2));

    }

    return ;

}

相关文章