虽然窝知道这题要用ST表,但我还是的用线段树…那咋了
#include<bits/stdc++.h>
using namespace std;
int tree[400005],n,a[100001],x,y,m;
void jianshu(int id,int l,int r){
if(l==r){
tree[id]=a[l];
return ;
}
int mid=(l+r)/2;
jianshu(id*2,l,mid);
jianshu(id*2+1,mid+1,r);
tree[id]=max(tree[id*2],tree[id*2+1]);
}
int find(int id,int l,int r){
if(x<=l&&y>=r) return tree[id];
int mid=(l+r)/2,ma=-1e9;
if(x<=mid) ma=max(ma,find(id*2,l,mid));
if(y>mid) ma=max(ma,find(id*2+1,mid+1,r));
return ma;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
jianshu(1,1,n);
for(int i=1;i<=m;i++){
cin>>x>>y;
cout<<find(1,1,n)<<endl;
}
}
题面
ST表是TLE56。
#include<bits/stdc++.h>
using namespace std;
int n,l,r,a[100005],m,st[100005][105];
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
st[i][0]=a[i];
}
for(int j=1;j<=log2(n);j++)
for(int i=1;i<=n-(1<<j)+1;i++)
st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
for(int i=1;i<=m;i++){
cin>>l>>r;
int s=log2(r-l+1);
cout<<max(st[l][s],st[r-(1<<s)+1][s])<<endl;
}
}
