目录
RMQ问题
RMQ（Range Maximum/Minimum Query）问题，即区间最值问题。
一般是多次询问，对时间复杂度要求高，一般需要 \(O(logn)\) 或 \(O(1)\) 复杂度
ST表
p[i][j] 是以i为起点，连续 \(2^j\) 个数字的最大值(是一个递推表)
| 3 | 9 | 4 | 2 | 1 | 6 | 8 | 5 | |
|---|---|---|---|---|---|---|---|---|
p[i][0] |
3 | 9 | 4 | 2 | 1 | 6 | 8 | 5 |
p[i][1] |
9 | 9 | 4 | 2 | 6 | 8 | 8 | - |
p[i][2] |
9 | 9 | 6 | 8 | 8 | - | - | - |
p[i][3] |
9 | - | - | - | - | - | - | - |
优缺点
优点：可查询，可在末尾插入删除
缺点：不能修改
实现
递推
\(p(i,j)=\max(p(i,j-1),p(i+2^{j-1},j-1))\)
查询
令 k = r-l+1;
int t = log2(k);
ans = max(p[l][t], p[r-(1<<t)+1][t]);
复杂度
\(O(logn+q)\)
代码
$\color{green}\text{点击查看代码}$
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#pragma GCC optimize (3) // O(3)
using namespace std;
int p[100010][20], lg[100010];
inline int read()
{
int x=0,f=1; char ch=getchar();
while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
while (ch>='0'&&ch<='9') { x=x*10+ch-48; ch=getchar(); }
return x*f;
}
int main()
{
ios::sync_with_stdio(false);
int n, m;
n=read();m=read();
for(int i = 1;i <= n;i++) p[i][0]=read();
for(int j = 1;(1<<j) <= n;j++)
for(int i = 1;i+(1<<j-1) <= n;i++)
p[i][j] = max(p[i][j-1], p[i+(1<<j-1)][j-1]);
lg[1] = 0;
for(int i = 2;i <= n;i++) lg[i] = lg[i>>1] + 1;
while(m--)
{
int l, r;
l=read();r=read();
int t = lg[r-l+1];
printf("%d\n",max(p[l][t], p[r-(1<<t)+1][t]));
}
return 0;
}
技巧-快速读入
inline int read()
{
int x=0,f=1; char ch=getchar();
while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
while (ch>='0'&&ch<='9') { x=x*10+ch-48; ch=getchar(); }
return x*f;
}
背下来就好了