无奖竞答：ST表

问题讨论区 提高段
1

ST表模板题

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[100005];
int f[100005][20];
int query(int l,int r){
	int g=log2(r-l+1);
	return max(f[l][g],f[r-(1<<g)+1][g]);
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		f[i][0]=a[i];
	}
	int lgn=log2(n);
	for(int j=1;j<=lgn;j++){
		for(int i=1;i<=n;i++){
			f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
		}
	}
	while(m--){
		int l,r;
		cin>>l>>r;
		cout<<query(l,r)<<endl;
	}
	return 0;
}
/*

*/
2

因该是这里

for(int i=1;i<=n;i++)

你的可能遍历到了f数组以外的地方，是RE吗？

1 个赞
3

RE30pts

4

所以f数组咋设才好

5

我看一眼

6

f开成原来的2倍试试看（不包对）

7

错误样例有吗

@杨思越

8

前三个对剩下全错

9

包错的 :roll_eyes:
还是RE30

10

改成
for(int i=1;i<=n-(1<<lgn)+1;i++)

11

局部截取_20250125_161245
所以应该根据这几个问题去改

12

遍历位置不对，

for(int i=1;i+(1<<k)-1<=n;i++)
13

或者i + (1 << j) - 1 <= n

14

循环改改，外层循环改成

for(int i=1;i<=n-(1<<j)+1;i++)

试试？

15

图片
好好好，只能输出9了QWQ

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[100005];
int f[100005][317];
int query(int l,int r){
	int g=log2(r-l+1);
	return max(f[l][g],f[r-(1<<g)+1][g]);
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		f[i][0]=a[i];
	}
	int lgn=log2(n);
	for(int j=1;j<=lgn;j++){
		for(int i=1;i<=n-(1<<lgn)+1;i++){
			f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
		}
	}
	while(m--){
		int l,r;
		cin>>l>>r;
		cout<<query(l,r)<<endl;
	}
	return 0;
}
/*

*/
16

@杨思越 转移式有问题

17

不是这样改的，应该改成

for(int i=1;i<=n-(1<<j)+1;i++)

可能就对了？（我也不清楚）

18

哦，看错了，好像没问题

19

董子豪说的是对的

20

TLE30pts
对的还是前三个
:roll_eyes:

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[100005];
int f[100005][20];
int query(int l,int r){
	int g=log2(r-l+1);
	return max(f[l][g],f[r-(1<<g)+1][g]);
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		f[i][0]=a[i];
	}
	int lgn=log2(n);
	for(int j=1;j<=lgn;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]);
		}
	}
	while(m--){
		int l,r;
		cin>>l>>r;
		cout<<query(l,r)<<endl;
	}
	return 0;
}
/*

*/