模板 - 数据结构 - ST表 + 二维ST表

区间最大值，$O(nlogn)$ 预处理，$O(1)$ 查询，不能动态修改。在查询次数M显著大于元素数量N的时候看得出差距。

令 $f[i][j]$ 表示 $[i,i+2^j-1]$ 的最大值。

显然， $f[i][0]=a[i]$ 。

根据定义式，写出状态转移方程： $f[i][j]=max(f[i][j-1],f[i+2^{j-1}][j-1])$ 。

我们可以这么理解：将区间 $[i,i+2^j-1]$ 分成相同的两部分

中点即为 $(i+(i+2^j-1))/2=i+2^{j-1}-1/2$

所以 $[i,i+2^j-1]$ 可以分成 $[i,i+2^{j-1}-1]$ 和 $[i+2^j,i+2^j-1]$

对于每个询问 $[x,y]$ ，我们把它分成两部分 $f[x][s],f[y-2^s+1][s]$

其中 $s=log_2(y-x+1)$ ，虽然这两个区间有重叠，但是重叠不会影响区间的最大值

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int MAXLOGN=;

const int MAXN=;

int a[MAXN+],f[MAXN+][MAXLOGN+1],Logn[MAXN+];

inline int read() {

    char c=getchar();

    int x=,f=;

    while(c<''||c>'') {

        if(c=='-')

            f=-;

        c=getchar();

    }

    while(c>=''&&c<='') {

        x=x*+c-'';

        c=getchar();

    }

    return x*f;

}

void init() {

    Logn[]=;

    Logn[]=;

    for(int i=; i<=MAXN; i++) {

        Logn[i]=Logn[i/]+;

    }

}

int main() {

    init();

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

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

        f[i][]=read();

    for(int j=; j<=MAXLOGN; j++)

        for(int i=; i+(<<j)-<=n; i++)

            f[i][j]=max(f[i][j-],f[i+(<<(j-))][j-]);

    for(int i=; i<=m; i++) {

        int x=read(),y=read();

        int s=Logn[y-x+];

        printf("%d\n",max(f[x][s],f[y-(<<s)+][s]));

    }

    return ;

}

二维：

#include<bits/stdc++.h>

using namespace std;

#define MAXN 501

int n,m;

int rec[MAXN][MAXN];

char dp[MAXN][MAXN][][];

char dp1[MAXN][MAXN][][];

inline int maxm(int a,int b,int c,int d) {

    if(a<b)

        a=b;

    if(a<c)

        a=c;

    if(a<d)

        a=d;

    return a;

}

inline int minm(int a,int b,int c,int d) {

    if(b<a)

        a=b;

    if(c<a)

        a=c;

    if(d<a)

        a=d;

    return a;

}

void st() {

    for(int k=; (<<k)<=n; k++)

        for(int l=; (<<l)<=m; l++)

            for(int i=; i+(<<k)-<=n; i++)

                for(int j=; j+(<<l)-<=m; j++) {

                    if(!k&&!l) {

                        dp1[i][j][k][l]=dp[i][j][k][l]=rec[i][j];

                    } else if(k==) {

                        dp[i][j][k][l]=max(dp[i][j][k][l-],dp[i][j+(<<(l-))][k][l-]);

                        dp1[i][j][k][l]=min(dp1[i][j][k][l-],dp1[i][j+(<<(l-))][k][l-]);

                    } else if(l==) {

                        dp[i][j][k][l]=max(dp[i][j][k-][l],dp[i+(<<(k-))][j][k-][l]);

                        dp1[i][j][k][l]=min(dp1[i][j][k-][l],dp1[i+(<<(k-))][j][k-][l]);

                    } else {

                        dp[i][j][k][l]=maxm(dp[i][j][k-][l-],dp[i+(<<(k-))][j][k-][l-],

                                            dp[i][j+(<<(l-))][k-][l-],dp[i+(<<(k-))][j+(<<(l-))][k-][l-]);

                        dp1[i][j][k][l]=minm(dp1[i][j][k-][l-],dp1[i+(<<(k-))][j][k-][l-],

                                             dp1[i][j+(<<(l-))][k-][l-],dp1[i+(<<(k-))][j+(<<(l-))][k-][l-]);

                    }

                    //printf("dp[%d][%d][%d][%d]=%d\n",i,j,k,l,dp[i][j][k][l]);

                }

}

int rmq2dmax(int x,int y,int x1,int y1) {

    int k=;

    while((x1-x+)>=(<<k))

        k++;

    k--;

    int l=;

    while((y1-y+)>=(<<l))

        l++;

    l--;

    return maxm(dp[x][y][k][l],dp[x1-(<<k)+][y][k][l],

                dp[x][y1-(<<l)+][k][l],dp[x1-(<<k)+][y1-(<<l)+][k][l]);

}

int rmq2dmin(int x,int y,int x1,int y1) {

    int k=;

    while((x1-x+)>=(<<k))

        k++;

    k--;

    int l=;

    while((y1-y+)>=(<<l))

        l++;

    l--;

    return minm(dp1[x][y][k][l],dp1[x1-(<<k)+][y][k][l],

                dp1[x][y1-(<<l)+][k][l],dp1[x1-(<<k)+][y1-(<<l)+][k][l]);

}

int main() {

    int g;

    scanf("%d%d%d",&n,&m,&g);

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

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

            scanf("%d",&rec[i][j]);

        }

    }

    st();

    for(int l=min(n,m); l; l--) {

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

            if(i+l->n)

                break;

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

                if(j+l->m)

                    break;

                int t=rmq2dmax(i,j,i+l-,j+l-)-rmq2dmin(i,j,i+l-,j+l-);

                if(t<=g){

                    printf("%d\n",l);

                    exit();

                }

            }

        }

    }

}