题解：AT_awc0005_e 山の高さ調査

· · 题解

提供三种做法。

线段树

显然，我们不需要 update 和 pushdown 操作，所以直接建树，区间查询即可。时间复杂度 \mathcal O(n \log n)。

但是我就是想写。

:::success[segment tree]

#include <bits/stdc++.h>
#define int long long
#define akcsps int mid=l+r>>1,ls=p<<1,rs=p<<1|1
using namespace std;
const int N=4e5+10;
int n,q;
int l,r;
int a[N];
int s[N],tag[N];
void build(int p,int l,int r){
    if(l==r){
        s[p]=a[l];
        return;
    }
    akcsps;
    build(ls,l,mid);
    build(rs,mid+1,r);
    s[p]=max(s[ls],s[rs]);
    return;
}
void pushdown(int p,int l,int r){
    if(!tag[p]) return;
    akcsps;
    a[ls]=max(a[ls],tag[p]);
    a[rs]=max(a[rs],tag[p]);
    a[p]=max(a[p],tag[p]);
    tag[ls]=max(tag[ls],tag[p]);
    tag[rs]=max(tag[rs],tag[p]);
    return;
}
void update(int p,int l,int r,int L,int R,int w){
    if(L<=l&&r<=R){
        s[p]=w;
        tag[p]=w;
        return;
    }
    akcsps;
    pushdown(p,l,r);
    if(L<=mid) update(ls,l,mid,L,R,w);
    if(R>mid) update(rs,mid+1,r,L,R,w);
    s[p]=max(s[ls],s[rs]);
    return;
}
int query(int p,int l,int r,int L,int R){
    if(L<=l&&r<=R)
        return s[p];
    akcsps;
    pushdown(p,l,r);
    int ans=0;
    if(L<=mid) ans=max(ans,query(ls,l,mid,L,R));
    if(R>mid) ans=max(ans,query(rs,mid+1,r,L,R));
    return ans;
}
signed main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;++i)
        cin>>a[i];
    build(1,1,n);
    while(q--){
        cin>>l>>r;
        cout<<query(1,1,n,l,r)<<'\n';
    }
    return 0;
}

:::

用时 44 ms。

分块

把块长定为 \sqrt{n}，如果询问区间覆盖了某些块，就记录整个块的最大值。最后剩余的区间暴力求解。

因为我太懒了，就没写 update 喵。

:::success[blocks]

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=4e5+10;
int n,q;
int l,r;
int a[N];
int block,b[N],mx[N];
void init(){
    block=sqrt(n);
    for(int i=1;i<=n;++i){
        b[i]=(i-1)/block+1;
        mx[b[i]]=max(mx[b[i]],a[i]);
    }
    return;
}
int query(int l,int r){
    int L=b[l],R=b[r];
    int ans=0;
    if(L==R){
        for(int i=l;i<=r;++i)
            ans=max(ans,a[i]);
        return ans;
    }
    for(int i=l;b[i]==L;++i) ans=max(ans,a[i]);
    for(int i=L+1;i<=R-1;++i) ans=max(ans,mx[i]);
    for(int i=r;b[i]==R;--i) ans=max(ans,a[i]);
    return ans;
}
signed main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;++i)
        cin>>a[i];
    init();
    while(q--){
        cin>>l>>r;
        cout<<query(l,r)<<'\n';
    }
    return 0;
}

:::

用时 86 ms。

ST 表

适用于不带修的 RMQ（区间最值）问题。

思想比较像线段树，就是把一段一段长度为 2 的指数的区间合并，查询时在 f_{l,x} 和 f_{r-x^2+1,x} 中取最值即可。

时间复杂度 \mathcal O((n+q) \log n)，主要瓶颈在预处理部分。

:::success[ST]

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=4e5+10,M=32;
int n,q;
int l,r;
int a[N];
int f[N][M];
void init(){
    for(int i=1;i<=n;++i)
        f[i][0]=a[i];
    for(int j=1;j<31;++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]);
    return;
}
int query(int l,int r){
    int x=log2(r-l+1);
    return max(f[l][x],f[r-(1<<x)+1][x]);
}
signed main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;++i)
        cin>>a[i];
    init();
    while(q--){
        cin>>l>>r;
        cout<<query(l,r)<<'\n';
    }
    return 0;
}

:::

用时 49 ms。