http://www.elijahqi.win/archives/504
日常复习模板x
st表（稀疏表）是解决RMQ问题一个常用的方法（写起来方便跑的也不慢.
主要思想应该是倍增以及区间dpdpdp .
以模板里求区间最大值为例，f[i][j]f[i][j]f[i][j] 表示区间 [i,i+2j{2^j}2j-1] 的答案.
考虑把区间分成两部分，于是dp[i][j]dp[i][j]dp[i][j] =max(dp[i][j−1]dp[i][j-1]dp[i][j−1],dp[i+2j−1][j−1]dp[i+2^{j-1}][j-1]dp[i+2j−1][j−1]).
dp[i][0]=a[i]dp[i][0]=a[i]dp[i][0]=a[i].
查询区间 [l,r][l,r][l,r] 时只要找一个k=floor(log2(r−l+1))k=floor(log_2 (r-l+1))k=floor(log2(r−l+1))，然后对f[l][k]f[l][k]f[l][k] 和 f[r−2k+1][k]f[r-2^k+1][k]f[r−2k+1][k] 取最值就好啦，这两个表示的恰好就是区间 [l,l+2k−1][l,l+2^k-1][l,l+2k−1] 和 [r−2k+1,r][r-2^k+1,r][r−2k+1,r].
预处理O(nlogn)O(nlogn)O(nlogn) ，单次查询O(1)O(1)O(1) ，总复杂度O(nlogn+m)O(nlogn+m)O(nlogn+m).
题目背景
这是一道ST表经典题——静态区间最大值
请注意最大数据时限只有0.8s，数据强度不低，请务必保证你的每次查询复杂度为 O(1)O(1) O(1)
题目描述
给定一个长度为 N N N 的数列，和 M M M 次询问，求出每一次询问的区间内数字的最大值。
输入输出格式
输入格式：
第一行包含两个整数 N,M N, M N,M ，分别表示数列的长度和询问的个数。
第二行包含 N N N 个整数（记为 ai a_i ai），依次表示数列的第 ii i 项。
接下来 M M M行，每行包含两个整数 li,ril_i, r_i li,ri，表示查询的区间为 [li,ri][ l_i, r_i] [li,ri]
输出格式：
输出包含 MM 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
说明
对于30%的数据，满足： 1≤N,M≤10 1 \leq N, M \leq 10 1≤N,M≤10
对于70%的数据，满足： 1≤N,M≤105 1 \leq N, M \leq {10}^5 1≤N,M≤105
对于100%的数据，满足： 1≤N≤105,1≤M≤106,ai∈[0,109],1≤li≤ri≤N 1 \leq N \leq {10}^5, 1 \leq M \leq {10}^6, a_i \in [0, {10}^9], 1 \leq l_i \leq r_i \leq N 1≤N≤105,1≤M≤106,ai∈[0,109],1≤li≤ri≤N
#include<cstdio>#define N 110000
inline int read(){
int x=0;char ch=getchar();
while (ch<'0'||ch>'9') ch=getchar();
while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();}
return x;
}
inline int max(int x,int y){
return x>y?x:y;
}
int Log[N],f[N][20],n,m;
inline int query(int x,int y){
int k=Log[y-x+1];
return max(f[x][k],f[y-(1<<k)+1][k]);
}
int main(){
// freopen("3865.in","r",stdin);
n=read();m=read();
for (int i=1;i<=n;++i) f[i][0]=read();Log[0]=-1;
for (int i=1;i<=n;++i) Log[i]=Log[i>>1]+1;
//for (int i=1;i<=n;++i) printf("%d,Log[i]);
for (int j=1;(1<<j)<=n;++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 a,b;
for (int i=1;i<=m;++i){
a=read();b=read();
printf("%d\n",query(a,b));
}
return 0;
}