经典问题，RMQ，不过为了增加一下文章长度，我打算贴一下题目

描述 Description

其实你们都不知道，小B是很小气的。一天小B带着他的弟弟小B’一起去摘果子，走着走着，他们忽然发现了一颗长满了果子的树。由于弟弟长得太矮了，弟弟只有让哥哥小B帮他摘一些果子下来。哥哥小B说:”弟弟啊，不是我不想给你摘多，我只是一次拿不了那么多，昨天晚上又没睡好，只能上一次树。所以哥哥只能给你摘一个哈。”没办法，弟弟只有答应了这个要求。
于是几下小B就上了树，树上的果子还真多，有N个呢！！但是小B很快发现这些果子大小不一。抠门的小B就想给自己拿个最大的，给弟弟拿个最小的果子。但是由于树上有些果子太高，小B不一定可以够着，所以他给你选了P个可以够着的果子区间，让你在这些区间里面找一个最大的果子和一个最小的果子。

输入格式 InputFormat

共p+2行，
第一行为n和p，
第二行为区间[1,n]的果子大小（用正整数表示）
后面p行形如a b，意为每次询问的区间的左界和右界

输出格式 OutputFormat

共p行，第i行为第i次询问时得到的最大值以及最小值（一个询问用空格空开max和min）

【注意】在输入数据中果子的大小是无序的。

样例输入 SampleInput [复制数据]

5 2
1 3 2 4 5
1 4
2 5

样例输出 SampleOutput [复制数据]

4 1
5 2

数据范围和注释 Hint

【数据范围】
保证果子大小不超过maxlongint
40%的数据： 1<=n,p<=1,000
100%的数据：1<=n<=50,000
1<=p<=20,000

有很多种解法啦，线段树也可以，之前我还写过一篇块状数组的也能解决这个问题，然后就是今天复习了一下st算法，所以就用st写了，关于st算法的话可以看看Archive里面的模版。

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
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>

using namespace std;

const int MN = 50010;

int st[MN][32][2];
int a[MN], pl[MN];
int n, m;

void stp(int n) {
    pl[1] = 0;
    for (int i = 2; i <= n; i++) {
        pl[i] = pl[i-1];
        if ((1 << (pl[i]+1)) == i) {
            pl[i]++;
        }
    }
    for (int i = n-1; i >= 0; i--) {
        st[i][0][0] = st[i][0][1] = a[i];
        for (int j = 1; (i + (1 << j) - 1) < n; j++) {
            st[i][j][0] = max(st[i][j-1][0], st[i + (1 << (j-1))][j-1][0]);
            st[i][j][1] = min(st[i][j-1][1], st[i + (1 << (j-1))][j-1][1]);
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    stp(n);
    int l, r, len, k, mx, mi;
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &l, &r);
        l--;
        r--;
        len = r-l+1;
        k = pl[len];
        mx = max(st[l][k][0], st[r-(1<<k)+1][k][0]);
        mi = min(st[l][k][1], st[r-(1<<k)+1][k][1]);
        printf("%d %d\n", mx, mi);
    }
    return 0;
}