DDOSvoid's Blog

Luogu P3865 【模板】ST表

发表于 分类于
本文字数： 885 阅读时长 ≈ 1 分钟
静态区间最大值

题目描述

https://www.luogu.com.cn/problem/P3865

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <cstdio>
#include <cctype>
#define maxn 100010
#define gc getchar
using namespace std;

int read() {
    int x = 0; char c = gc();
    while (!isdigit(c)) c = gc();
    while (isdigit(c)) x = x * 10 + c - '0', c = gc();
    return x;
}

int n, m, a[maxn];

int Log[maxn], st[maxn][21];
void init_st() { Log[0] = -1;
    for (int i = 1; i <= n; ++i) Log[i] = Log[i >> 1] + 1, st[i][0] = a[i];
    for (int j = 1; j <= 20; ++j)
        for (int i = 1; i + (1 << j) - 1 <= n; ++i)
            st[i][j] = max(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);
}

int query(int l, int r) {
    int k = Log[r - l + 1];
    return max(st[l][k], st[r - (1 << k) + 1][k]);
}

int main() {
    n = read(); m = read(); 
    for (int i = 1; i <= n; ++i) a[i] = read(); 
    init_st(); 
    for (int i = 1; i <= m; ++i) {
        int l = read(), r = read();
        printf("%d\n", query(l, r));
    }
    return 0;
}