题解：P3865 【模板】ST 表 && RMQ 问题

· · 题解

这是一篇线段树题解。

虽然题目的查询复杂度必须为 O(1)，而线段树查询复杂度 O(\log n)，但我偏不信邪，试一试才知道。

前置知识

线段树，模板题传送门。

具体实现

根据题面意思，很容易就可以写出建树，查询的部分。其实和加法的逻辑是一样的。

注意到，这道题目不需要修改数值，所以就没有懒标记、修改函数。最难的懒标记都没有了，剩下的岂不是简简单单。

由于线段树常数较大，且查询复杂度为 O(\log n)，那么就需要用到快读优化，我在题面给的快读上又加了一点小小的改动：

inline int read(){
    int x = 0, f = 1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
    //改动的地方，把 x*10+ch-48 用位运算表示，这样速度会更快一点。 
    return x * f;
}

代码

于是我们就轻轻松松卡常过了这道题目，下面是代码。

#include <bits/stdc++.h>
#define ld p << 1
#define rd p << 1 | 1
using namespace std;
const int N = 1e5 + 5;
inline int read(){
    int x = 0, f = 1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
    return x * f;
}
struct Node{
    int l, r, zd;
} t[N << 2];
int n, Q, a[N];
void push_up(int p){
    t[p].zd = max(t[ld].zd, t[rd].zd);
}
void build(int p, int l, int r){//建树 
    t[p] = (Node) {l, r, a[l]};
    if(l == r) return;
    int mid = l + r >> 1;
    build(ld, l, mid);
    build(rd, mid + 1, r);
    push_up(p);
}
int ask(int p, int l, int r){//查询 
    if(l <= t[p].l && t[p].r <= r){
        return t[p].zd;
    }
    int mid = t[p].l + t[p].r >> 1, ans = -1;
    if(l <= mid) ans = max(ans, ask(ld, l, r));
    if(r > mid) ans = max(ans, ask(rd, l, r));
    return ans;
}
int main(){
    n = read(), Q = read();
    for(int i = 1;i <= n;i++) a[i] = read();
    build(1, 1, n);
    while(Q--){
        int l = read(), r = read();
        printf("%d\n", ask(1, l, r));
    }
    return 0;
}

不过既然这是 ST 表的模板题，肯定要尊重一下，下面贴一下正解，如何实现可以去看其他题解。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
inline int read(){
    int x = 0, f = 1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
    return x * f;
}
int n, m, lg[N], f[N][22];
int main(){
    n = read(), m = read();
    for(int i = 2;i <= n;i++) lg[i] = lg[i / 2] + 1;
    for(int i = 1;i <= n;i++){
        f[i][0] = read();
    }
    for(int j = 1;j <= lg[n];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]);
        }
    }
    for(int i = 1;i <= m;i++){
        int l = read(), r = read(), lgc, maxl, maxr;
        lgc = lg[r - l + 1];
        maxl = f[l][lgc], maxr = f[r - (1 << lgc) + 1][lgc];
        printf("%d\n", max(maxl, maxr));
    }
    return 0;
}