POJ2019

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

int N,B,K;int mm[505];int val[maxn][maxn];int dpmin[maxn][maxn][8][8];int dpmax[maxn][maxn][8][8];

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

dpmin和dpmax就是预处理数组了

然后看一下开局预处理：

void initRMQ(int n,int m){    for(int i=1;i<=n;i++)    for(int j=1;j<=m;j++)        dpmin[i][j][0][0]=dpmax[i][j][0][0]=val[i][j];    for(int ii=0;ii<=mm[n];ii++)    for(int jj=0;jj<=mm[m];jj++)    if(ii+jj)    for(int i=1;i+(1<
     
      <=n;i++)    for(int j=1;j+(1<
      
       <=m;j++)    {        if(ii)        {            dpmin[i][j][ii][jj] = min(dpmin[i][j][ii-1][jj],dpmin[i+(1<<(ii-1))][j][ii-1][jj]);            dpmax[i][j][ii][jj] = max(dpmax[i][j][ii-1][jj],dpmax[i+(1<<(ii-1))][j][ii-1][jj]);        }        else        {            dpmin[i][j][ii][jj] = min(dpmin[i][j][ii][jj-1],dpmin[i][j+(1<<(jj-1))][ii][jj-1]);            dpmax[i][j][ii][jj] = max(dpmax[i][j][ii][jj-1],dpmax[i][j+(1<<(jj-1))][ii][jj-1]);        }    }}
      
     

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

mm[0]=-1;    for(int i=1;i<=500;i++)        mm[i]=((i&(i-1))==0)?mm[i-1]+1:mm[i-1];

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

int rmq1(int x1,int y1,int x2,int y2)  //max{    int k1=mm[x2-x1+1];    int k2=mm[y2-y1+1];    x2=x2-(1<

这个式子确实很长的

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

1 #include
     
       2 #include
      
        3 using namespace std; 4 const int maxn=255; 5 int N,B,K; 6 int mm[505]; 7 int val[maxn][maxn]; 8 int dpmin[maxn][maxn][8][8]; 9 int dpmax[maxn][maxn][8][8];10 void initRMQ(int n,int m)11 {12     for(int i=1;i<=n;i++)13     for(int j=1;j<=m;j++)14         dpmin[i][j][0][0]=dpmax[i][j][0][0]=val[i][j];15     for(int ii=0;ii<=mm[n];ii++)16     for(int jj=0;jj<=mm[m];jj++)17     if(ii+jj)18     for(int i=1;i+(1<
       
        <=n;i++)19     for(int j=1;j+(1<
        
         <=m;j++)20     {21         if(ii)22         {23             dpmin[i][j][ii][jj] = min(dpmin[i][j][ii-1][jj],dpmin[i+(1<<(ii-1))][j][ii-1][jj]);24             dpmax[i][j][ii][jj] = max(dpmax[i][j][ii-1][jj],dpmax[i+(1<<(ii-1))][j][ii-1][jj]);25         }26         else27         {28             dpmin[i][j][ii][jj] = min(dpmin[i][j][ii][jj-1],dpmin[i][j+(1<<(jj-1))][ii][jj-1]);29             dpmax[i][j][ii][jj] = max(dpmax[i][j][ii][jj-1],dpmax[i][j+(1<<(jj-1))][ii][jj-1]);30         }31     }32 }33 int rmq1(int x1,int y1,int x2,int y2)  //max34 {35     int k1=mm[x2-x1+1];36     int k2=mm[y2-y1+1];37     x2=x2-(1<