题目描述

从前有个人名叫 WNB，他有着天才般的记忆力，他珍藏了许多许多的宝藏。

在他离世之后留给后人一个难题（专门考验记忆力的啊！），如果谁能轻松回答出这个问题，便可以继承他的宝藏。

题目是这样的：给你一大串数字（编号为 $1$ 到 $N$，大小可不一定哦！），在你看过一遍之后，它便消失在你面前，随后问题就出现了，给你 $M$ 个询问，每次询问就给你两个数字 $A,B$，要求你瞬间就说出属于 $A$ 到 $B$ 这段区间内的最大数。

一天，一位美丽的姐姐从天上飞过，看到这个问题，感到很有意思（主要是据说那个宝藏里面藏着一种美容水，喝了可以让这美丽的姐姐更加迷人），于是她就竭尽全力想解决这个问题。

但是，她每次都以失败告终，因为这数字的个数是在太多了！

于是她请天才的你帮他解决。如果你帮她解决了这个问题，可是会得到很多甜头的哦！

输入格式

第一行一个整数 $N$ 表示数字的个数。

接下来一行为 $N$ 个数，表示数字序列。

第三行读入一个 $M$，表示你看完那串数后需要被提问的次数。

接下来 $M$ 行，每行都有两个整数 $A,B$。

输出格式

输出共 $M$ 行，每行输出一个数，表示对一个问题的回答。

数据范围

$1 \\le N \\le 2 \\times 10^5$,
$1 \\le M \\le 10^4$,
$1 \\le A \\le B \\le N$。

输入样例：

6
34 1 8 123 3 2
4
1 2
1 5
3 4
2 3

输出样例：

34
123
123
8

算法1

(ST) $O(n\log n+m)$

首先，这题不用修改，所以可以用 ST 算法（Sparse Table，又称ST表）来做。ST 本质上是基于倍增思想的动态规划。

预处理

设 $a$ 是要求区间最值的数列，$s[i,j]=\max\{a[i],a[i+1],\ldots,a[i+2^j-1]\}$。显然，$s[i,0]=a[i]$。
根据定义，可以推出 $\forall j\in N$，$s[i,j]=\max\{s[i,j-1],s[i+2^{j-1},j-1]\}$。这样就可以在 $O(n\log n)$ 的时间内推出所有合法的 $s$ 值。

查找

回到正题上来，如何找到 $\max\{a[l],a[l+1],\ldots,a[r]\}$ 的值呢？
设 $k=|\{a[l],a[l+1],\ldots,a[r]\}|=r-l+1$，可以发现，$2\cdot 2^{\lfloor\log_2(k)\rfloor}=2^{\lfloor\log_2(k)\rfloor+1}>r-l+1$，并且 $2^{\lfloor\log_2(k)\rfloor}\le r-l+1$，所以 $\max\{a[l],a[l+1],\ldots,a[r-1]\}=\max\{\max\{a[l],a[l+1],\ldots,a[l+2^{\lfloor\log_2(k)\rfloor}-1]\},\max\{a[r-2^{\lfloor\log_2(k)\rfloor}],a[r-2^{\lfloor\log_2(k)\rfloor}+1],\ldots,a[r-1]\}\}$
$O(1)$ 得到答案。

图示：（鼠标画的可能有点不好看）

时间复杂度

整个算法初始化需要 $O(n\log n)$ 的时间，每次查询需要 $O(1)$ 的时间，$m$ 次查询共花了 $O(m)$ 的时间，总共的时间复杂度是 $O(n\log n+m)$（在此题中，$m<n\log n$，所以也可以看成 $O(n\log n)$）。

空间复杂度

s数组一共用了 $O(n\log n)$ 的空间。

C++ 代码

#include <iostream>

using namespace std;

const int N = 200010, M = 20; // 为啥 M = 20？lg(2 × 10⁵) ≈ 18，为了保险再加 2

int n, m;
int s[N][M]; // ST

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> s[i][0]; // 边界情况：s[i, 0] = a[i]，直接读入
    for (int i = 1; 1 << i <= n; i ++ ) // 注意维度的顺序
        for (int j = 0; j + (1 << i) <= n; j ++ )
            s[j][i] = max(s[j][i - 1], s[j + (1 << i - 1)][i - 1]); // 如上

    cin >> m;
    while (m -- )
    {
        int l, r;
        cin >> l >> r;

        int k = __lg(r - l + 1); // __lg(x) = ⌊log₂(x)⌋
        cout << max(s[l - 1][k], s[r - (1 << k)][k]) << '\n'; // 如上
    }

    return 0;
}

算法2

(线段树) $O((n+m)\log n)$

知 周 所 众

线段树支持区间查询

那么我们就可以用线段树做这题了

时间复杂度

初始化 $O(n\log n)$，查询每次 $O(\log n)$，一共查 $m$ 次，就是 $O(m\log n)$。
把初始化的时间和查询的时间加起来，得到 $O((n+m)\log n)$ 。

空间复杂度

线段树的空间复杂度当然是 $O(n)$ 啦！

C++ 代码

#include <iostream>

using namespace std;

const int N = 200010, INF = 1 << 30;

int n, m;
struct Node
{
    int l, r;
    int maxv; // 这道题中维护的信息：最大值（因为这道题没有修改，所以不用懒标记和 pushdown 这些东西了）
}tr[N * 4]; // 记得要开 4 倍空间

void pushup(int u) // 根据子节点的信息推断出当前节点的信息
{
    tr[u].maxv = max(tr[u << 1].maxv, tr[u << 1 | 1].maxv);
}

void build(int u, int l, int r)
{
    if (l == r)
    {
        int x;
        cin >> x, tr[u] = {l, r, x}; // 边建树边读
        return ;
    }

    tr[u] = {l, r};
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);

    pushup(u); // 别忘了 pushup 一下
}

int query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].maxv; // 如果这个区间被包含在查询区间里，直接返回 maxv

    int maxv = -INF; // 存结果
    if (tr[u << 1].r >= l) maxv = query(u << 1, l, r); // 如果查询区间和当前区间的左儿子相交
    if (tr[u << 1].r < r) maxv = max(maxv, query(u << 1 | 1, l, r)); // 如果查询区间和当前区间的右儿子相交

    return maxv;
}

int main()
{
    cin >> n;

    build(1, 1, n); // 建树

    cin >> m;
    while (m -- ) // 查询
    {
        int l, r;
        cin >> l >> r;
        cout << query(1, l, r) << '\n';
    }

    return 0;
}

算法3

(RMQ标准算法) $O(n+m)$

太累了，明天再写……

时间复杂度

write here…

空间复杂度

write here…

C++ 代码

my code...