天才的记忆

题目链接：https://ac.nowcoder.com/acm/problem/50449

算法一（线段树）

    我们很容易发现这是一道关于区间查询的问题，并且这道题没有区间修改或者单点修改，因此线段树中只有区间查询的操作。因此无脑写线段树即可，时间复杂度为$O((n+m)logn)O((n+m)logn)$

Code:

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;
const int N=2e5+5;
int n,m;
int w[N];
struct Node{
    int l,r;
    int sum;//区间最大值
}tr[N<<2];
void pushup(int u){
    tr[u].sum=max(tr[u<<1].sum,tr[u<<1|1].sum);
}
void build(int u,int l,int r){
    if(l==r) tr[u]={l,l,w[l]};
    else{
        tr[u]={l,r};
        int mid=l+r>>1;
        build(u<<1,l,mid);
        build(u<<1|1,mid+1,r);
        pushup(u);
    }
}
int query(int u,int l,int r){
    if(tr[u].l>=l&&tr[u].r<=r) return tr[u].sum;
    else{
        int mid=tr[u].l+tr[u].r>>1;
        int res=-1e9;
        if(l<=mid) res=max(res,query(u<<1,l,r));
        if(r>mid)  res=max(res,query(u<<1|1,l,r));
        return res;
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>w[i];
    build(1,1,n);
    cin>>m;
    while(m--){
        int x,y;
        cin>>x>>y;
        cout<<query(1,x,y)<<endl;
    }
    return 0;
}

算法二（st表）

    我们首先预处理出2^0,2^1……2^M的区间最大值，对于每个查询[l,r],首先找到最大的一个满足2^k<len的k，其中len=r-l+1,结合数学知识，我们可以得到k=log(len)/log(2),则最大值就是在[l,l+2^k]和[r-2^k+1,r]中取最大值即可,时间复杂度$O(nlogn+m)O(nlogn+m)$
Code:

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>

using namespace std;
const int N=2e5+5,M=18;
int w[N];
int f[N][M];
int n,m;
void init(){
    for(int j=0;j<M;j++)
        for(int i=1;i+(1<<j)-1<=n;i++)
            if(!j) f[i][j]=w[i];
            else f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);
}
int query(int l,int r){
    int len=r-l+1;
    int k=log(len)/log(2);
    return max(f[l][k],f[r-(1<<k)+1][k]);
    
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>w[i];
    init();
    cin>>m;
    while(m--){
        int l,r;
        cin>>l>>r;
        cout<<query(l,r)<<endl;
    }
    return 0;
}