RMQ [POJ3368Frequent values]

http://poj.org/problem?id=3368

一维RMQ

//询问递增序列 [l,r] 间,出现次数最多的数的个数,分段后用RMQ询问最小值
int id, d[MM][17], N, Q;
int len[MM],pos[MM],b[MM];

int log_2(int x) {
    int res=0;
    while(x>>=1) res++;
    return res;
}
void get_rmq() {
    int i,j,k,limit;
    for(i=1;i<=id;i++) d[i][0]=len[i];
    k=log_2(id);
    for(i=1;i<=k;i++) {
        limit=id-(1<<i)+1;
        for(j=1;j<=limit;j++) {
            d[j][i]=max(d[j][i-1],d[j+(1<<i>>1)][i-1]);
        }
    }
}
void get_data() {
    int i,j,k,a,pre=maxint;
    scanf("%d",&Q);
    memset(len,0,sizeof(len));
    for(i=id=0;i<N;i++) {
        scanf("%d",&a);
        if(a!=pre) id++,pre=a,b[id]=i;;
        pos[i]=id;
        len[id]++;
    }
    get_rmq();
    for(i=1;i<=id;i++) b[i]+=len[i];
}
//query
int query(int ll,int rr) {
    int k=log_2(rr-ll+1);
    return max(d[ll][k],d[rr-(1<<k)+1][k]);
}

void solve() {
    int i,j,k,l,r;
    while(Q--) {
        scanf("%d%d",&l,&r);
        l--,r--;
        if(pos[l]==pos[r])  printf("%d\n",r-l+1);
        else if(pos[l]+1==pos[r])    printf("%d\n",max(b[pos[l]]-l,r-b[pos[l]]+1));
        else {
            int mi=query(pos[l]+1,pos[r]-1);
            int tmp=max(b[pos[l]]-l,r-b[pos[r]-1]+1);
            printf("%d\n",max(tmp,mi));
        }
    }
}

int main() {
    while(scanf("%d",&N),N) get_data(),solve();
    return 0;
}

 二维RMQ

const int MM = 305;
int n, m;
bool flag;
int maze[MM][MM];
int dp[MM][MM][9][9];
int id[MM];

int Log_2(int x) {
  int res = 1, cnt = 0;
  while(res <= x) res <<= 1,cnt++;
  return cnt-1;
}

void get_data() {
  for(int i = 1;i <= n; i++)
      for(int j = 1;j <= m; j++) 
          scanf("%d",&maze[i][j]);
}

void get_init() {
  id[0] = -1;
  for(int i = 1;i < MM;i++) 
      id[i] = Log_2(i);
} 
/************************
二维RMQ的模版题
用dp[row][col][i][j]表示(row,col) 
到(row+2^i,col+2^j)的最小值
///////////////////////////////
查询时：
int kx = log_2(x2-x1+1);
int ky = log_2(y2-y1+1);
去下面四个的最小值：
int m1 = dp[x1][y1][kx][ky];
int m2 = dp[x2-(1<<kx)+1][y1][kx][ky];
int m3 = dp[x1][y2-(1<<ky)+1][kx][ky];
int m4 = dp[x2-(1<<kx)+1][y2-(1<<ky)+1][kx][ky];
*************************/
////////////////初始化/////////////
void init_Rmq() {
   int i, j, row, col, limt_row;
   
   for(i = 1;i <= n;i++) 
       for(j = 1;j <= m;j++)
           dp[i][j][0][0] = maze[i][j]; 

       int k1 = id[n], k2 = id[m];
       for(i = 0;i <= k1; i++) 
           for(j = 0;j <= k2; j++) {
               if(i==0 && j==0) continue;
               for(row = 1;row+(1<<i)-1 <= n;row++) { 
                   limt_row = row+(1<<(i-1));
                   for(col = 1;col+(1<<j)-1 <= m;col++) { 
                       if(i == 0) {
                         dp[row][col][i][j]=f_max(dp[row][col][i][j-1],dp[row][col+(1<<(j-1))][i][j-1]);
                       } else {
                          dp[row][col][i][j]=f_max(dp[row][col][i-1][j],dp[limt_row][col][i-1][j]);
                       }
                   }
               }
           }
}
///////////////////////询问最大值/////////////
int Query(int x1,int x2,int y1,int y2) {
  int kx = id[x2-x1+1]; 
  int ky = id[y2-y1+1];
  int xx2, yy2;
  xx2 = x2-(1<<kx)+1; yy2 = y2-(1<<ky)+1;
  int m1 = dp[x1][y1][kx][ky];
  int m2 = dp[xx2][y1][kx][ky];
  int m3 = dp[x1][yy2][kx][ky]; 
  int m4 = dp[xx2][yy2][kx][ky]; 
//  printf("%d %d %d\n",kx,ky,Log_2(1));
//  printf("%d %d %d %d\n",m1,m2,m3,m4);
  int ans= f_max(f_max(m1,m2),f_max(m3,m4)); 
  if(ans==maze[x1][y1] || ans==maze[x1][y2] || ans==maze[x2][y1] || ans==maze[x2][y2]) flag = true;
  return ans;
}
//////////////////////////////////////
void solve() {
   int q, x1, y1, x2, y2;
   init_Rmq();
   scanf("%d", &q);
   while(q--) {
      flag = false;
      scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
      printf("%d ",Query(x1,x2,y1,y2));
      puts(flag?"yes":"no");
   }
}
 
int main() {
    get_init();
    while(scanf("%d%d",&n,&m)!=EOF) get_data(),solve();
 return 0;
}