【洛谷3865】 【模板】ST表

猫树

实测跑的比ST表快！！！

这个东西也是$O(1)$的，不会可以看我上一篇Blog

/*
  mail: mleautomaton@foxmail.com
  author: MLEAutoMaton
  This Code is made by MLEAutoMaton
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define ll long long
#define re register
#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
inline int gi()
{
    int f=1,sum=0;char ch=getchar();
    while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
    return f*sum;
}
const int N=500010;
int lg[N],mx[21][N],pos[N<<2],a[N],n,m;
void build(int o,int l,int r,int dep)
{
    if(l==r)return (void)(pos[l]=o);
    int mid=(l+r)>>1;
    mx[dep][mid]=a[mid];
    for(int i=mid-1;i>=l;i--)
        mx[dep][i]=max(mx[dep][i+1],a[i]);
    mx[dep][mid+1]=a[mid+1];
    for(int i=mid+2;i<=r;i++)
        mx[dep][i]=max(mx[dep][i-1],a[i]);
    build(o<<1,l,mid,dep+1);
    build(o<<1|1,mid+1,r,dep+1);
}
int query(int l,int r)
{
    if(l==r)return a[l];
    int dep=lg[pos[l]]-lg[pos[l]^pos[r]];
    return max(mx[dep][l],mx[dep][r]);
}
int main()
{
    n=gi();m=gi();
    for(int i=1;i<=n;i++)a[i]=gi();
    int L=2;
    while(L<n)L<<=1;
    for(int i=2;i<=L<<1;i++)lg[i]=lg[i>>1]+1;
    build(1,1,L,1);
    while(m--){int l=gi(),r=gi();printf("%d\n",query(l,r));}
    return 0;
}