题解：AT_awc0005_e 山の高さ調査

____JOINthing · 2026-11-09 21:52:58 · 题解

静态区间求最值的板子，当然可以用 ST 表，不过线段树其实也不长。

不用修改，仅需 build，query，函数就可以实现，非常简单。

版子实在没啥讲的了，看看咋写吧。

时间复杂度：O(n\log n)。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mid (l+r>>1)
const int N=1e5+5;
int n,q,a[N],tr[N*4];
void build(int u,int l,int r){
    if(l==r){tr[u]=a[l];return;}
    build(u*2,l,mid);
    build(u*2|1,mid+1,r);
    tr[u]=max(tr[u*2],tr[u*2|1]);
}
int query(int u,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr)return tr[u];
    int res=0;
    if(ql<=mid)res=max(res,query(u*2,l,mid,ql,qr));
    if(qr>mid)res=max(res, query(u*2|1,mid+1,r,ql,qr));
    return res;
}
signed main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>a[i];
    build(1,1,n);
    while(q--){
        int l,r;cin>>l>>r;
        cout<<query(1,1,n,l,r)<<'\n';
    }
    return 0;
}