题目描述

输入一串数字，给你 M 个询问，每次询问就给你两个数字 X,Y，要求你说出 X 到 Y 这段区间内的最大数。

输入格式
第一行两个整数 N,M 表示数字的个数和要询问的次数；

接下来一行为 N 个数；

接下来 M 行，每行都有两个整数 X,Y。

输出格式
输出共 M 行，每行输出一个数。

数据范围
1≤N≤105,
1≤M≤106,
1≤X≤Y≤N,
数列中的数字均不超过231−1

样例

输入样例：
10 2
3 2 4 5 6 8 1 2 9 7
1 4
3 8
输出样例：
5
8

算法1

ST算法

C++ 代码

#include<iostream>
#include<cmath>
#define max(a, b)a > b ? a : b

const int space = 1e5 + 7;
int dp[space][34] = { {} };//dp[i][j]表示从i开始长度为2^(j-1)中的答案，当然不包括第i + 2^(j-1)的数据；
int lenth[34] = {};
int log_2[33] = {};
int N, M;

int main(void)
{
    lenth[0] = 1;
    for (int i = 1; i < 31; i++)lenth[i] = lenth[i - 1] << 1;
    scanf("%d %d", &N, &M);
    for (int i = 1; i <= N; i++)scanf("%d", &dp[i][0]);

    for (int idx = 1; lenth[idx] <= N; idx++)
        for (int now = 1; now + lenth[idx] <= N + 1; now++)
            dp[now][idx] = max(dp[now][idx - 1], dp[now + lenth[idx - 1]][idx - 1]);

    while (M--)
    {
        int left, right;
        scanf("%d %d", &left, &right);
        int k = right - left + 1;
        k = log(k) / log(2);//计算log2(k),从left+lenth[k]要小于等于right，否则会有不确定的数据
        while (left + lenth[k] < right - lenth[k] + 1)k++;//注了这段代码也可以AC，写成这样更容易理解且更保险；
        printf("%d\n", max(dp[left][k], dp[right - lenth[k] + 1][k]));
    }

    return 0;
}

算法2

树状数组

C++ 代码

#include<iostream>
#include<algorithm>

int lowest_bit(int n) { return n & (-n); }
//求长度，例如i==8，等于 1000B ，则该数组单元包括了data[8]本身的数据，
//而二进制又有三个零，所以又包括了i之前的七个数据，加上本身的数据就是2^3 =8；
const int space = 1e6 + 7;
int ali[space] = {}, al[space] = {};//ali数组是保存树状数组的值，而al数组保存的是每个单元的数据
//若该题是求区间和的话，应该通过al数组来修改ali数组才行 --- 减去之前的数据，加上更改的数据
int N, M;

void updata(int pos, int data, int arr_len)
{
    //核心代码：lowest_bit()
    //该树的父节点，即包含该单元的下一个结点就是 i + lowest_bit(i)；
    for (int i = pos; i <= arr_len; i += lowest_bit(i))
        ali[i] = std::max(ali[i], data);
    return;
}

int query(int left, int right)
{
    int max_ans = -0x7f7f7f7f, i = right;
    for (; i >= left && i - lowest_bit(i) + 1 >= left; i -= lowest_bit(i))//递推到头
        max_ans = std::max(max_ans, ali[i]);
    while (i >= left)若i还是大于等于left则还没有枚举完成，继续枚举
    {
        max_ans = std::max(max_ans, al[i]);
        if (i - lowest_bit(i) + 1 < left)i--;
        else
        {
            max_ans = std::max(max_ans, ali[i]);
            i -= lowest_bit(i);
        }
    }
    return max_ans;
}

int main(void)
{
    scanf("%d %d", &N, &M);
    for (int i = 1; i <= N; i++)
    {
        scanf("%d", &al[i]);
        updata(i, al[i], N);
    }
    while (M--)
    {
        int x, y;
        scanf("%d %d", &x, &y);
        printf("%d\n", query(x, y));
    }
    return 0;
}

算法3

线段树（没有AC，应该是代码太繁琐了）

C++ 代码

#include<iostream>
#define max(a ,b) a > b ? a : b

const int space = 1e5 + 7;
const int INF = -0x7f7f7f7f;
int ali[space] = {};
int seg_tree[space << 3 + 7] = {};
int N, M;

int build_segtree(int left, int right, int root)
{
    if (left == right)return seg_tree[root] = ali[left];
    int mid = (left + right) >> 1;
    return seg_tree[root] =
        max(build_segtree(left, mid, root << 1),
            build_segtree(mid + 1, right, (root << 1) + 1));
}

int query(int left_now, int right_now, int left_ans, int right_ans, int root)
{
    if (left_ans <= left_now && right_ans >= right_now)return seg_tree[root];
    int mid = (left_now + right_now) >> 1, maxv = INF;
    if (mid >= left_ans)maxv = query(left_now, mid, left_ans, right_ans, root << 1);
    if (mid < right_ans)maxv = max(maxv,query(mid + 1, right_now, left_ans, right_ans, (root << 1) + 1));
    return maxv;
}

int main(void)
{
    scanf("%d %d", &N, &M);
    for (int i = 1; i <= N; i++)scanf("%d", &ali[i]);
    build_segtree(1, N, 1);
    int x, y;
    while (M--)
    {
        scanf("%d %d", &x, &y);
        printf("%d\n", query(1, N, x, y, 1));
    }
    return 0;
}