数据结构：二维ST表

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

POJ2019

我们其实是很有必要把ST算法拓展到二维的，因为二维的RMQ问题还是不少的

int N,B,K;

int mm[];

int val[maxn][maxn];

int dpmin[maxn][maxn][][];

int dpmax[maxn][maxn][][];

这里的N是方阵的长宽，此处是正方形题目，然后mm是预处理出来的，方便计算指数

dpmin和dpmax就是预处理数组了

然后看一下开局预处理：

void initRMQ(int n,int m)

{

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

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

        dpmin[i][j][][]=dpmax[i][j][][]=val[i][j];

    for(int ii=;ii<=mm[n];ii++)

    for(int jj=;jj<=mm[m];jj++)

    if(ii+jj)

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

    for(int j=;j+(<<jj)-<=m;j++)

    {

        if(ii)

        {

            dpmin[i][j][ii][jj] = min(dpmin[i][j][ii-][jj],dpmin[i+(<<(ii-))][j][ii-][jj]);

            dpmax[i][j][ii][jj] = max(dpmax[i][j][ii-][jj],dpmax[i+(<<(ii-))][j][ii-][jj]);

        }

        else

        {

            dpmin[i][j][ii][jj] = min(dpmin[i][j][ii][jj-],dpmin[i][j+(<<(jj-))][ii][jj-]);

            dpmax[i][j][ii][jj] = max(dpmax[i][j][ii][jj-],dpmax[i][j+(<<(jj-))][ii][jj-]);

        }

    }

}

我们看预处理的时候还是比较明朗的，当然别忘了在主函数把mm初始化好

    mm[]=-;

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

        mm[i]=((i&(i-))==)?mm[i-]+:mm[i-];

然后就是求最大值和最小值的函数了，这里，一定要仔细地去写，很容易写错：

int rmq1(int x1,int y1,int x2,int y2)  //max

{

    int k1=mm[x2-x1+];

    int k2=mm[y2-y1+];

    x2=x2-(<<k1)+;

    y2=y2-(<<k2)+;

    return max(max(dpmax[x1][y1][k1][k2],dpmax[x1][y2][k1][k2]),max(dpmax[x2][y1][k1][k2],dpmax[x2][y2][k1][k2]));

}

int rmq2(int x1,int y1,int x2,int y2)

{

    int k1=mm[x2-x1+];

    int k2=mm[y2-y1+];

    x2=x2-(<<k1)+;

    y2=y2-(<<k2)+;

    return min(min(dpmin[x1][y1][k1][k2],dpmin[x1][y2][k1][k2]),min(dpmin[x2][y1][k1][k2],dpmin[x2][y2][k1][k2]));

}

这个式子确实很长的

最后给出题目完整的实现：

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 const int maxn=;

 int N,B,K;

 int mm[];

 int val[maxn][maxn];

 int dpmin[maxn][maxn][][];

 int dpmax[maxn][maxn][][];

 void initRMQ(int n,int m)

 {

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

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

         dpmin[i][j][][]=dpmax[i][j][][]=val[i][j];

     for(int ii=;ii<=mm[n];ii++)

     for(int jj=;jj<=mm[m];jj++)

     if(ii+jj)

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

     for(int j=;j+(<<jj)-<=m;j++)

     {

         if(ii)

         {

             dpmin[i][j][ii][jj] = min(dpmin[i][j][ii-][jj],dpmin[i+(<<(ii-))][j][ii-][jj]);

             dpmax[i][j][ii][jj] = max(dpmax[i][j][ii-][jj],dpmax[i+(<<(ii-))][j][ii-][jj]);

         }

         else

         {

             dpmin[i][j][ii][jj] = min(dpmin[i][j][ii][jj-],dpmin[i][j+(<<(jj-))][ii][jj-]);

             dpmax[i][j][ii][jj] = max(dpmax[i][j][ii][jj-],dpmax[i][j+(<<(jj-))][ii][jj-]);

         }

     }

 }

 int rmq1(int x1,int y1,int x2,int y2)  //max

 {

     int k1=mm[x2-x1+];

     int k2=mm[y2-y1+];

     x2=x2-(<<k1)+;

     y2=y2-(<<k2)+;

     return max(max(dpmax[x1][y1][k1][k2],dpmax[x1][y2][k1][k2]),max(dpmax[x2][y1][k1][k2],dpmax[x2][y2][k1][k2]));

 }

 int rmq2(int x1,int y1,int x2,int y2)

 {

     int k1=mm[x2-x1+];

     int k2=mm[y2-y1+];

     x2=x2-(<<k1)+;

     y2=y2-(<<k2)+;

     return min(min(dpmin[x1][y1][k1][k2],dpmin[x1][y2][k1][k2]),min(dpmin[x2][y1][k1][k2],dpmin[x2][y2][k1][k2]));

 }

 int main()

 {

     mm[]=-;

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

         mm[i]=((i&(i-))==)?mm[i-]+:mm[i-];

     while(scanf("%d%d%d",&N,&B,&K)==)

     {

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

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

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

         initRMQ(N,N);

         int x,y;

         while(K--)

         {

             scanf("%d%d",&x,&y);

             printf("%d\n",rmq1(x,y,x+B-,y+B-)-rmq2(x,y,x+B-,y+B-));

         }

     }

     return ;

 }

相关文章