题解 P3865 【【模板】ST表】

SimonGreenall · 2017-11-09 08:11:22 · 题解

这题。。。说好的“请注意最大数据时限只有0.8s，数据强度不低，请务必保证你的每次查询复杂度为 O(1) “呢。。。

事实是一发线段树就可以了（额。。其实ST表还是更方便些的，我就是欠抽了想拿线段树卡过它），而且并不用zkw线段树，0.6s。。。

#include <iostream>
#include <cstdio>
using namespace std;
inline int read(void) {
    int x=0,f=1; char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=-1;
    for(;ch>='0'&&ch<='9';x=(x<<3)+(x<<1)+(ch^48),ch=getchar());
    return x*f;
}
const int maxn=4e5+9;
struct Tree {
    int l,r,mid,max;
}tree[maxn];
void build(int num, int l, int r) {
    tree[num].l=l,tree[num].r=r;
    tree[num].mid=(l+r)>>1;
    tree[num].max=-0x3f3f3f;
    if(l<r){
        build(num<<1,l,tree[num].mid);
        build(num<<1|1,tree[num].mid+1,r);
    }
}
void insert(int num, int cnt, int x) {
    tree[num].max=max(tree[num].max,x);
    if(tree[num].l!=tree[num].r){
        if(cnt<=tree[num].mid) insert(num<<1,cnt,x);
        else insert(num<<1|1,cnt,x);
    }
}
int query(int num, int l, int r) {
    if(l<=tree[num].l&&tree[num].r<=r)
        return tree[num].max;
    int maxx=-0x3f3f3f;
    if(l<=tree[num].mid) maxx=max(maxx,query(num<<1,l,r));
    if(tree[num].mid<r) maxx=max(maxx,query(num<<1|1,l,r));
    return maxx;
}
int main(int argc, char const *argv[]) {
    int n=read(),m=read();
    build(1,1,n);
    for(int i=1;i<=n;i++){
        int x=read(); insert(1,i,x);
    }
    for(int i=1;i<=m;i++){
        int l=read(),r=read();
        printf("%d\n",query(1,l,r));
    }
    return 0;
}