前置芝士
用倍增思想求静态区间最值(无法求和)。
d p [ i ] [ k ] dp[i][k] dp[i][k]表示区间 [ i , i + 2 k − 1 ] [i,i+2^k-1] [i,i+2k−1]的最大或最小值。
预处理 O ( n log n ) O(n\log n) O(nlogn)
则 d p [ i ] [ 0 ] = a [ i ] dp[i][0]=a[i] dp[i][0]=a[i]。则：
d p [ i ] [ j ] = m i n / m a x ( d p [ i ] [ j − 1 ] , d p [ i + 2 j − 1 ] [ j − 1 ] ) dp[i][j]=min/max(dp[i][j-1],dp[i+2^{j-1}][j-1]) dp[i][j]=min/max(dp[i][j−1],dp[i+2j−1][j−1])
- 要注意边界是 i + 2 j − 1 < = n i+2^j-1<=n i+2j−1<=n，即当前枚举到的区间右端点不能超过 n n n，否则会指针乱跑访问非法空间。
- 要先枚举 j j j，再循环 i i i，否则会访问到未处理区间。
其意义是对于 [ i , i + 2 j − 1 ] [i,i+2^j-1] [i,i+2j−1]这个区间，将其拆分成前后两段2的次幂的，如图。
查询 O ( 1 ) O(1) O(1)
设 k = log 2 ( r − l + 1 ) k=\log_2(r-l+1) k=log2(r−l+1)，即长度不超过总长的最大2的次幂的长度。则：
Q ( l , r ) = m a x / m i n ( d p [ l ] [ k ] , d p [ r − 2 k + 1 ] [ k ] ) Q(l,r)=max/min(dp[l][k],dp[r-2^k+1][k]) Q(l,r)=max/min(dp[l][k],dp[r−2k+1][k])
查询时从左端点向左查最大不超过总长的2的次幂，与从右端点向左查同长，再将两个答案取最值即可。
参考代码(模板题)
#include<bits/stdc++.h>
#define ll long long//记得开long long
using namespace std;
const int MAXN=1e5+10;
int Q,a[MAXN],dp[MAXN][20],n;
void init(){
for(int i=1;i<=n;i++) dp[i][0]=a[i];
for(int j=1;j<20;j++)//j的上限为logn，需要灵活调整
for(int i=1;i+(1<<j)-1<=n;i++)
dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
}
int LOG[MAXN];
int query(int l,int r){
int k=LOG[r-l+1];
return max(dp[l][k],dp[r-(1<<k)+1][k]);
}
int main()
{
for(int i=0;i<1e5;i++) LOG[i]=log2(i);
scanf("%d%d",&n,&Q);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
init();int l,r;
while(Q--){
scanf("%d%d",&l,&r);
printf("%d\n",query(l,r));
}
}
使用注意事项
千万不要 M L E MLE MLE，宁可 R E RE RE少拿几个点也不要冲内存的极限。
注意边界