**************************************************************************************************************
一维RMQ查找最大值下标模板
一维RMQ模版
二维RMQ模板
**************************************************************************************************************
①一维RMQ查找最大值下标模板
int n,q;
int val[N];
int mx[20][N];
int tlog[N];
int p[21];
void make_maxrmq() {
int i,j,k;
for(i=1;i<=n;i++) mx[0][i]=i;
for(j=1;p[j]<=n;j++)
for(i=1;i+p[j]-1<=n;i++) {
if(val[ mx[j-1][i] ]>val[ mx[j-1][i+p[j-1]] ])
mx[j][i]=mx[j-1][i];
else
mx[j][i]=mx[j-1][i+p[j-1]];
}
}
int maxrmq(int a,int b) {
int k=tlog[b-a+1];
int ret;
if(val[ mx[k][a] ]>val[ mx[k][b-p[k]+1] ]) ret=mx[k][a];
else ret=mx[k][b-p[k]+1];
return ret;
}
void init_rmq() {
for(int i=0;i<=20;i++) p[i]=(1<<i);
tlog[0]=-1;
for(int i=1;i<=50000;i++)
tlog[i]=(i&(i-1))?tlog[i-1]:tlog[i-1]+1;
}
**************************************************************************************************************
②一维RMQ模版
int n,q;
int a[N];
int mx[20][N],mi[20][N];
int tlog[N];
int p[21];
void make_maxrmq() {
int i,j,k;
for(i=1;i<=n;i++) mx[0][i]=a[i];
for(j=1;p[j]<=n;j++)
for(i=1;i+p[j]-1<=n;i++)
mx[j][i]=max(mx[j-1][i],mx[j-1][i+p[j-1]]);
}
void make_minrmq() {
int i,j,k;
for(i=1;i<=n;i++) mi[0][i]=a[i];
for(j=1;p[j]<=n;j++)
for(i=1;i+p[j]-1<=n;i++)
mi[j][i]=min(mi[j-1][i],mi[j-1][i+p[j-1]]);
}
int maxrmq(int a,int b) {
int k=tlog[b-a+1];
return max(mx[k][a],mx[k][b-p[k]+1]);
}
int minrmq(int a,int b) {
int k=tlog[b-a+1];
return min(mi[k][a],mi[k][b-p[k]+1]);
}
void init() {
for(int i=0;i<=20;i++) p[i]=(1<<i);
tlog[0]=-1;
for(int i=1;i<=50000;i++)
tlog[i]=(i&(i-1))?tlog[i-1]:tlog[i-1]+1;
}
int main()
{
init();
int s,t;
while(scanf("%d%d",&n,&q)!=EOF) {
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
make_maxrmq();
make_minrmq();
while(q--) {
scanf("%d%d",&s,&t);
printf("%d\n",maxrmq(s,t)-minrmq(s,t));
}
}
}
**************************************************************************************************************
③二维RMQ模板
==========================================================================================
①【普通版】
int n,m,q;
int a[N][N];
int mx[10][10][N][N];
int tlog[N];
int p[11];
void make_maxrmq() {
int i,j,k,l;
for(i=0;i<=n;i++)
for(j=0;j<=m;j++)
mx[0][0][i][j]=a[i][j];
for(i=0;p[i]<=n;i++) {
int di=p[i];
for(j=0;p[j]<=m;j++) {
if(i==0&&j==0) continue;
int dj=p[j];
for(k=1;k+di-1<=n;k++) {
for(l=1;l+dj-1<=m;l++) {
if(i==0)
mx[i][j][k][l]=max(mx[i][j-1][k][l],mx[i][j-1][k][l+p[j-1]]);
else
mx[i][j][k][l]=max(mx[i-1][j][k][l],mx[i-1][j][k+p[i-1]][l]);
}
}
}
}
}
int maxrmq(int x1,int x2,int y1,int y2) {
int kn=tlog[x2-x1+1]; //(int)(log(x2-x1+1.0)/log(2.0));
int km=tlog[y2-y1+1]; //(int)(log(y2-y1+1.0)/log(2.0));
int v1=mx[kn][km][x1][y1];
int v2=mx[kn][km][x1][y2-p[km]+1];
int v3=mx[kn][km][x2-p[kn]+1][y1];
int v4=mx[kn][km][x2-p[kn]+1][y2-p[km]+1];
return max(max(v1,v2),max(v3,v4));
}
void init_rmq() {
for(int i=0;i<=10;i++) p[i]=1<<i;
tlog[0]=-1;
for(int i=1;i<=300;i++)
tlog[i]=(i&(i-1))?tlog[i-1]:tlog[i-1]+1;
}
int main()
{
init_rmq();
int i,j;
int x1,x2,y1,y2;
while(scanf("%d%d",&n,&m)!=EOF) {
for(i=1;i<=n;i++)
for(j=1;j<=m;j++) scan_d(a[i][j]);
make_maxrmq();
scanf("%d",&q);
while(q--) {
scan_d(x1); scan_d(y1);
scan_d(x2); scan_d(y2);
int ans=maxrmq(x1,x2,y1,y2);
printf("%d ",ans);
if(ans==a[x1][y1]||ans==a[x1][y2]||ans==a[x2][y1]||ans==a[x2][y2])
puts("yes");
else
puts("no");
}
}
return 0;
}
==========================================================================================
②【终极版】
//数组优化:四维降三维
//二维RMQ，区间求最值
// + tlog[] 优化
int n,m,q;
int val[N][N];
int mx[10][N][N];
int tlog[N];
int pw[11];
void make_maxrmq() {
int i,j,k;
int nn=max(n,m);
for(k=0;pw[k]<=nn;k++)
for(i=1;i<=n;i++)
for(j=1;j<=m;j++) mx[k][i][j]=val[i][j];
for(k=1;pw[k]<=nn;k++) {
for(i=1;i<=n;i++) {
for(j=1;j<=m;j++) {
mx[k][i][j]=mx[k-1][i][j];
if(i+pw[k-1]<=n)
mx[k][i][j]=max(mx[k][i][j],mx[k-1][i+pw[k-1]][j]);
if(j+pw[k-1]<=m)
mx[k][i][j]=max(mx[k][i][j],mx[k-1][i][j+pw[k-1]]);
if(i+pw[k-1]<=n&&j+pw[k-1]<=m)
mx[k][i][j]=max(mx[k][i][j],mx[k-1][i+pw[k-1]][j+pw[k-1]]);
}
}
}
}
int maxrmq(int x1,int y1,int x2,int y2) {
int i=tlog[x2-x1+1]; //(int)(log(x2-x1+1.0)/log(2.0));
int j=tlog[y2-y1+1]; //(int)(log(y2-y1+1.0)/log(2.0));
int k=min(i,j);
if(i>j) i=j;
int ret=mx[0][x1][y1];
for(i=x1;i<=x2;i+=pw[k]) {
if(i+pw[k]>x2) i=x2-pw[k]+1;
for(j=y1;j<=y2;j+=pw[k]) {
if(j+pw[k]>y2) j=y2-pw[k]+1;
ret=max(ret,mx[k][i][j]);
}
}
return ret;
}
void init_rmq() {
for(int i=0;i<=10;i++) pw[i]=1<<i;
tlog[0]=-1;
for(int i=1;i<=300;i++)
tlog[i]=(i&(i-1))?tlog[i-1]:tlog[i-1]+1;
}
int main()
{
init_rmq();
int i,j;
int x1,x2,y1,y2;
while(scanf("%d%d",&n,&m)!=EOF) {
for(i=1;i<=n;++i)
for(j=1;j<=m;++j) scan_d(val[i][j]);
make_maxrmq();
scanf("%d",&q);
while(q--) {
scan_d(x1); scan_d(y1);
scan_d(x2); scan_d(y2);
int ret=maxrmq(x1,y1,x2,y2);
printf("%d ",ret);
if(ret==val[x1][y1]||ret==val[x1][y2]||ret==val[x2][y1]||ret==val[x2][y2])
puts("yes");
else
puts("no");
}
}
return 0;
}
**************************************************************************************************************
**************************************************************************************************************