一.st取区间最大值
模板题洛谷P3865:https://www.luogu.com.cn/problem/P3865
注意点:
1.f[i][j]=f[i][i+2j-1]
2.预处理时是以2的次幂进行跳的取区间最大值
3.query询问函数:
询问时取的len的方法是由:2x<=r-l+1来取的,由于不是等于号所以f[i][j-1],f[i+(1<<(j-1))][j-1]一定是包含了整个区间的,只是可能有重复贡献问题,但是由于是取最大值,所以重复贡献并不影响结果
#include <bits/stdc++.h> using namespace std; const int maxn=1e5+10; const int lgn=21;//取法是总值的2lgn int f[maxn][lgn]; int lg[maxn]; void init() { lg[1]=0,lg[2]=1; for(int i=3;i<maxn;++i){ lg[i]=lg[i>>1]+1; } } void st(int n) { for(int j=1; j<=lgn; ++j) for(int i=1; i+(1<<j)-1<=n; ++i) f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]); } int query(int l,int r) { int len=lg[r-l+1]; // int len=log(r-l+1)/log(2); return max(f[l][len],f[r-(1<<len)+1][len]); } int main() { init(); int n,m; scanf("%d%d",&n,&m); for(int i=1; i<=n; ++i) scanf("%d",&f[i][0]); st(n); for(int i=1; i<=m; ++i) { int l,r; scanf("%d%d",&l,&r); printf("%d ",query(l,r)); } return 0; }