一、一维RMQ：
前两天学lca的时候学了这个东西，今天再来系统的学一下。
P3865 【模板】ST表：
题目背景
这是一道ST表经典题——静态区间最大值
请注意最大数据时限只有0.8s，数据强度不低，请务必保证你的每次查询复杂度为 O(1)
题目描述
给定一个长度为 N 的数列，和 M 次询问，求出每一次询问的区间内数字的最大值。
输入格式
第一行包含两个整数 N, M 分别表示数列的长度和询问的个数。
第二行包含 N 个整数依次表示数列的第 i 项。
接下来 M行，每行包含两个整数 l, r，表示查询的区间为 [ l, r]
输出格式
输出包含 M行，每行一个整数，依次表示每一次询问的结果。
输入输出样例
输入 #1 复制
8 8
9 3 1 7 5 6 0 8
1 6
1 5
2 7
2 6
1 8
4 8
3 7
1 8
输出 #1 复制
9
9
7
7
9
8
7
9
n<=1e5，m<=1e6
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
#include<vector>
#define ll long long
#define llu unsigned ll
using namespace std;
const int maxn=101000;
int f[maxn][20],a[maxn], _log[maxn];
int n,m;
void ST(void)
{
for(int i=1;i<=n;i++)
f[i][0]=a[i],_log[i]=log(i)/log(2);
//还有另一种求log的方法；
_log[0]=-1;
for(int i=1;i<=n;i++)
{
f[i][0]=a[i];
_log[i]=(i&(i-1))==0?_log[i-1]+1:_log[i-1];
}
int t=_log[n]+1;
//int t=_log[n];
//上述两种t的取值范围均可
for(int j=1;j<=t;j++)
{
for(int i=1;i<=n-(1<<j)+1;i++)
f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
}
int get_max(int l,int r)
{
int k=_log[r-l+1];
return max(f[l][k],f[r-(1<<k)+1][k]);
}
int main(void)
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
ST();
int x,y;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
printf("%d\n",get_max(x,y));
}
return 0;
}
二、二维RMQ：
二维RMQ有两种写法，一种是单独处理每一行，另一种是直接处理整个矩阵。
前者预处理时间复杂度为O（n * m * logn），查询时间复杂度为O（n）。
后者预处理时间复杂度为O（n * m * logn * logm），查询时间复杂度为O（1）。
①Cornfields POJ - 2019 ：
FJ has decided to grow his own corn hybrid in order to help the cows make the best possible milk. To that end, he’s looking to build the cornfield on the flattest piece of land he can find.
FJ has, at great expense, surveyed his square farm of N x N hectares (1 <= N <= 250). Each hectare has an integer elevation (0 <= elevation <= 250) associated with it.
FJ will present your program with the elevations and a set of K (1 <= K <= 100,000) queries of the form “in this B x B submatrix, what is the maximum and minimum elevation?”. The integer B (1 <= B <= N) is the size of one edge of the square cornfield and is a constant for every inquiry. Help FJ find the best place to put his cornfield.
Input
-
Line 1: Three space-separated integers: N, B, and K.
-
Lines 2…N+1: Each line contains N space-separated integers. Line 2 represents row 1; line 3 represents row 2, etc. The first integer on each line represents column 1; the second integer represents column 2; etc.
-
Lines N+2…N+K+1: Each line contains two space-separated integers representing a query. The first integer is the top row of the query; the second integer is the left column of the query. The integers are in the range 1…N-B+1.
Output -
Lines 1…K: A single integer per line representing the difference between the max and the min in each query.
Sample Input
5 3 1
5 1 2 6 3
1 3 5 2 7
7 2 4 6 1
9 9 8 6 5
0 6 9 3 9
1 2
Sample Output
5
求某个小举行内最大值与最小值的差值。这个题的矩形是正方形，只给左上角坐标和边长。
//每一行分别RMQ
//313ms
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<deque>
#include<set>
#include<vector>
#define ll long long
#define llu unsigned ll
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=260;
int a[maxn][maxn];
int f[2][maxn][maxn][8];
int _log[maxn];
int n,m,len;
void st(void)
{
_log[0]=-1;
for(int i=1;i<=n;i++)
{
_log[i]=(i&(i-1))==0?_log[i-1]+1:_log[i-1];
for(int j=1;j<=n;j++)
f[0][i][j][0]=f[1][i][j][0]=a[i][j];
}
int t=_log[n];
for(int i=1;i<=n;i++)
{
for(int k=1;k<=t;k++)
{
for(int j=1;j<=n-(1<<k)+1;j++)
{
f[0][i][j][k]=max(f[0][i][j][k-1],f[0][i][j+(1<<(k-1))][k-1]);
f[1][i][j][k]=min(f[1][i][j][k-1],f[1][i][j+(1<<(k-1))][k-1]);
}
}
}
}
int ask(int x,int y,int len)
{
int t=_log[len];
int yy=y+len-1;
int maxx=-inf,minn=inf;
for(int i=x;i<=x+len-1;i++)
{
maxx=max(maxx,max(f[0][i][y][t],f[0][i][yy-(1<<t)+1][t]));
minn=min(minn,min(f[1][i][y][t],f[1][i][yy-(1<<t)+1][t]));
}
return maxx-minn;
}
int main(void)
{
while(scanf("%d%d%d",&n,&len,&m)!=EOF)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
scanf("%d",&a[i][j]);
}
st();
int x,y;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
printf("%d\n",ask(x,y,len));
}
}
return 0;
}
//矩形RMQ
//782ms
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<deque>
#include<set>
#include<vector>
#define ll long long
#define llu unsigned ll
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=260;
int a[maxn][maxn];
int f[2][maxn][maxn][8][8];
int _log[maxn];
int n,m,len;
void st(void)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
f[0][i][j][0][0]=f[1][i][j][0][0]=a[i][j];
}
int t1=_log[n];
int t2=_log[n];
for(int k=0;k<=t1;k++)
{
for(int l=0;l<=t2;l++)
{
if(k==0&&l==0) continue;
for(int i=1;i<=n-(1<<k)+1;i++)
{
for(int j=1;j<=n-(1<<l)+1;j++)
{
if(k)
{
f[0][i][j][k][l]=max(f[0][i][j][k-1][l],f[0][i+(1<<(k-1))][j][k-1][l]);
f[1][i][j][k][l]=min(f[1][i][j][k-1][l],f[1][i+(1<<(k-1))][j][k-1][l]);
}
else
{
f[0][i][j][k][l]=max(f[0][i][j][k][l-1],f[0][i][j+(1<<(l-1))][k][l-1]);
f[1][i][j][k][l]=min(f[1][i][j][k][l-1],f[1][i][j+(1<<(l-1))][k][l-1]);
}
}
}
}
}
}
int ask(int x1,int y1,int x2,int y2)
{
int t1=_log[x2-x1+1];
int t2=_log[y2-y1+1];
x2=x2-(1<<t1)+1;
y2=y2-(1<<t2)+1;
int maxx=max(max(f[0][x1][y1][t1][t2],f[0][x1][y2][t1][t2]),max(f[0][x2][y1][t1][t2],f[0][x2][y2][t1][t2]));
int minn=min(min(f[1][x1][y1][t1][t2],f[1][x1][y2][t1][t2]),min(f[1][x2][y1][t1][t2],f[1][x2][y2][t1][t2]));
return maxx-minn;
}
int main(void)
{
_log[0]=-1;
for(int i=1;i<maxn;i++)
_log[i]=(i&(i-1))==0?_log[i-1]+1:_log[i-1];
while(scanf("%d%d%d",&n,&len,&m)!=EOF)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
scanf("%d",&a[i][j]);
}
st();
int x,y;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
printf("%d\n",ask(x,y,x+len-1,y+len-1));
}
}
return 0;
}
②Check Corners HDU - 2888：
Paul draw a big m*n matrix A last month, whose entries Ai,j are all integer numbers ( 1 <= i <= m, 1 <= j <= n ). Now he selects some sub-matrices, hoping to find the maximum number. Then he finds that there may be more than one maximum number, he also wants to know the number of them. But soon he find that it is too complex, so he changes his mind, he just want to know whether there is a maximum at the four corners of the sub-matrix, he calls this “Check corners”. It’s a boring job when selecting too many sub-matrices, so he asks you for help. (For the “Check corners” part: If the sub-matrix has only one row or column just check the two endpoints. If the sub-matrix has only one entry just output “yes”.)
Input
There are multiple test cases.
For each test case, the first line contains two integers m, n (1 <= m, n <= 300), which is the size of the row and column of the matrix, respectively. The next m lines with n integers each gives the elements of the matrix which fit in non-negative 32-bit integer.
The next line contains a single integer Q (1 <= Q <= 1,000,000), the number of queries. The next Q lines give one query on each line, with four integers r1, c1, r2, c2 (1 <= r1 <= r2 <= m, 1 <= c1 <= c2 <= n), which are the indices of the upper-left corner and lower-right corner of the sub-matrix in question.
Output
For each test case, print Q lines with two numbers on each line, the required maximum integer and the result of the “Check corners” using “yes” or “no”. Separate the two parts with a single space.
Sample Input
4 4
4 4 10 7
2 13 9 11
5 7 8 20
13 20 8 2
4
1 1 4 4
1 1 3 3
1 3 3 4
1 1 1 1
Sample Output
20 no
13 no
20 yes
4 yes
//每一行分别RMQ
//6130ms
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<deque>
#include<set>
#include<vector>
#define ll long long
#define llu unsigned ll
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=310;
int a[maxn][maxn];
int f[maxn][maxn][10];
int _log[maxn];
int n,m;
void st(void)
{
_log[0]=-1;
for(int i=1;i<=m;i++)
_log[i]=(i&(i-1))==0?_log[i-1]+1:_log[i-1];
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
f[i][j][0]=a[i][j];
}
int t=_log[m];
for(int i=1;i<=n;i++)
{
for(int k=1;k<=t;k++)
{
for(int j=1;j<=m-(1<<k)+1;j++)
{
f[i][j][k]=max(f[i][j][k-1],f[i][j+(1<<(k-1))][k-1]);
}
}
}
}
int ask(int x1,int y1,int x2,int y2)
{
int t=_log[y2-y1+1];
int maxx=-inf;
for(int i=x1;i<=x2;i++)
{
maxx=max(maxx,max(f[i][y1][t],f[i][y2-(1<<t)+1][t]));
}
return maxx;
}
int main(void)
{
while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
scanf("%d",&a[i][j]);
}
st();
int q;
scanf("%d",&q);
int x1,y1,x2,y2;
for(int i=1;i<=q;i++)
{
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
int cm=ask(x1,y1,x2,y2);
printf("%d ",cm);
if(cm==a[x1][y1]||cm==a[x1][y2]||cm==a[x2][y2]||cm==a[x2][y1])
printf("yes\n");
else printf("no\n");
}
}
return 0;
}
有点卡空间，不过刚刚好能开
//每个矩形最大值
//3432ms
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<deque>
#include<set>
#include<vector>
#define ll long long
#define llu unsigned ll
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=310;
int a[301][301];
int f[301][301][9][9];
int _log[maxn];
int n,m;
void st(void)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
f[i][j][0][0]=a[i][j];
}
int t1=_log[n];
int t2=_log[m];
for(int k=0;k<=t1;k++)
{
for(int l=0;l<=t2;l++)
{
if(k==0&&l==0) continue;
for(int i=1;i<=n-(1<<k)+1;i++)
{
for(int j=1;j<=m-(1<<l)+1;j++)
{
if(k)
f[i][j][k][l]=max(f[i][j][k-1][l],f[i+(1<<(k-1))][j][k-1][l]);
else f[i][j][k][l]=max(f[i][j][k][l-1],f[i][j+(1<<(l-1))][k][l-1]);
}
}
}
}
}
int ask(int x1,int y1,int x2,int y2)
{
int t1=_log[x2-x1+1];
int t2=_log[y2-y1+1];
x2=x2-(1<<t1)+1;
y2=y2-(1<<t2)+1;
return max(max(f[x1][y1][t1][t2],f[x1][y2][t1][t2]),max(f[x2][y1][t1][t2],f[x2][y2][t1][t2]));
}
int main(void)
{
_log[0]=-1;
for(int i=1;i<=305;i++)
_log[i]=(i&(i-1))==0?_log[i-1]+1:_log[i-1];
while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
scanf("%d",&a[i][j]);
}
st();
int q;
scanf("%d",&q);
int x1,y1,x2,y2;
for(int i=1;i<=q;i++)
{
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
int cm=ask(x1,y1,x2,y2);
printf("%d ",cm);
if(cm==a[x1][y1]||cm==a[x1][y2]||cm==a[x2][y2]||cm==a[x2][y1])
printf("yes\n");
else printf("no\n");
}
}
return 0;
}
京公网安备 11010502036488号