一.st取区间最大值
模板题洛谷P3865:https://www.luogu.com.cn/problem/P3865
注意点:
1.f[i][j]=f[i][i+2j-1]
2.预处理时是以2的次幂进行跳的取区间最大值
3.Q询问函数:
询问时取的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=1e6+10; const int lgn=21;取法是总值的2lgn int f[maxn][lgn]; void st() { 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 Q(int l,int r) { int len=log(r-l+1)/log(2); return max(f[l][len],f[r-(1<<len)+1][len]); } int main() { int n,m; ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>m; for(int i=1; i<=n; ++i) cin>>f[i][0]; for(int i=1; i<=m; ++i) { int l,r; cin>>l>>r; cout<<Q(l,r)<<endl; } return 0; }
原文:https://www.cnblogs.com/waryan/p/12237061.html