区间最大值,$O(nlogn)$ 预处理,$O(1)$ 查询, 不能动态修改. 在查询次数 M 显著大于元素数量 N 的时候看得出差距.
令 $f[i][j]$ 表示 $[i,i+2^j-1]$ 的最大值.
显然, $f[i][0]=a[i]$ .
根据定义式, 写出状态转移方程: $f[i][j]=max(f[i][j-1],f[i+2^{j-1}][j-1])$ .
我们可以这么理解: 将区间 $[i,i+2^j-1]$ 分成相同的两部分
中点即为 $(i+(i+2^j-1))/2=i+2^{j-1}-1/2$
所以 $[i,i+2^j-1]$ 可以分成 $[i,i+2^{j-1}-1]$ 和 $[i+2^j,i+2^j-1]$
对于每个询问 $[x,y]$ , 我们把它分成两部分 $f[x][s],f[y-2^s+1][s]$
其中 $s=log_2(y-x+1)$ , 虽然这两个区间有重叠, 但是重叠不会影响区间的最大值
- #include <bits/stdc++.h>
- using namespace std;
- #define ll long long
- const int MAXLOGN=17;
- const int MAXN=100000;
- int a[MAXN+5],f[MAXN+5][MAXLOGN],Logn[MAXN+5];
- inline int read() {
- char c=getchar();
- int x=0,f=1;
- while(c<'0'||c>'9') {
- if(c=='-')
- f=-1;
- c=getchar();
- }
- while(c>='0'&&c<='9') {
- x=x*10+c-'0';
- c=getchar();
- }
- return x*f;
- }
- void init() {
- Logn[1]=0;
- Logn[2]=1;
- for(int i=3; i<=MAXN; i++) {
- Logn[i]=Logn[i/2]+1;
- }
- }
- int main() {
- init();
- int n=read(),m=read();
- for(int i=1; i<=n; i++)
- f[i][0]=read();
- for(int j=1; j<=MAXLOGN; 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]);
- for(int i=1; i<=m; i++) {
- int x=read(),y=read();
- int s=Logn[y-x+1];
- printf("%d\n",max(f[x][s],f[y-(1<<s)+1][s]));
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2988965.html