# 体验RMQ

`#include<cstdio>#include<iostream>#include<cstdlib>#include<cmath>using namespace std;short M[251][251][9];short F[251][251][9];inline short max4(int a,int b,int c,int d){ int ma; if(max(a,b)>=max(c,d))ma=max(a,b); else ma=max(c,d); return ma;}inline short min4(int a,int b,int c,int d){ int mi; if(min(a,b)<=min(c,d))mi=min(a,b); else mi=min(c,d); return mi;}int main(){ int N; int B; int K; int x; int y; scanf("%d%d%d",&N,&B,&K); for(int i=1; i<=N; i++) for(int j=1; j<=N; j++) { scanf("%d",&F[i][j][0]); M[i][j][0]=F[i][j][0]; } for(int n=1; (1<<(n-1))<=B; n++) for(int i=1; i+(1<<n)-1<=N; i++) for(int j=1; j+(1<<n)-1<=N; j++) { F[i][j][n]=max4(F[i][j][n-1], F[i+(1<<(n-1))][j][n-1], F[i][j+(1<<(n-1))][n-1], F[i+(1<<(n-1))][j+(1<<(n-1))][n-1]); M[i][j][n]=min4(M[i][j][n-1], M[i+(1<<(n-1))][j][n-1], M[i][j+(1<<(n-1))][n-1], M[i+(1<<(n-1))][j+(1<<(n-1))][n-1]); } int KK=(int)(log2(B)); for(int i=1; i<=K; i++) { scanf("%d%d",&x,&y); short max=max4(F[x][y][KK], F[x+B-(1<<KK)][y][KK], F[x][y+B-(1<<KK)][KK], F[x+B-(1<<KK)][y+B-(1<<KK)][KK]); short min=min4(M[x][y][KK], M[x+B-(1<<KK)][y][KK], M[x][y+B-(1<<KK)][KK], M[x+B-(1<<KK)][y+B-(1<<KK)][KK]); printf("%d/n",(max-min)); } system("pause"); return 0;}`

`总结：1，大数组（特别是多维）应该在main以外定义，否则系统承受不了；     2，发现将cin/cout改写为scanf/printf后速度提升相当大，直接从700ms降到188ms；`

Top