【题目来源】
https://www.acwing.com/problem/content/1272/

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

【输入格式】
第一行两个整数 N，M，表示数字的个数和要询问的次数；
接下来一行为 N 个数；
接下来 M 行，每行都有两个整数 X，Y。

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

【数据范围】
1≤N≤10^5，
1≤M≤10^6，
1≤X≤Y≤N，
数列中的数字均不超过 2^31−1。

【输入样例】
10 2
3 2 4 5 6 8 1 2 9 7
1 4
3 8

【输出样例】
5
8

【算法分析】
ST算法详见：https://blog.csdn.net/hnjzsyjyj/article/details/103429761
本题的ST算法求解代码详见：https://blog.csdn.net/hnjzsyjyj/article/details/120479214

【算法代码：线段树】

#include <bits/stdc++.h>
using namespace std;

const int N=1e5+5;
int a[N];
int n,m;

struct Node {
    int le,ri;
    int imx;
} tr[N*4];

void pushup(int u) {
    tr[u].imx=max(tr[u<<1].imx,tr[u<<1|1].imx);
}

void build(int u,int le,int ri) {
    if(le==ri) tr[u]= {le,ri,a[ri]};
    else {
        tr[u]= {le,ri};
        int mid=(le+ri)>>1;
        build(u<<1,le,mid);
        build(u<<1|1,mid+1,ri);
        pushup(u);
    }
}

int query(int u,int le,int ri) {
    if(tr[u].le>=le && tr[u].ri<=ri) {
        return tr[u].imx;
    }

    int mid=(tr[u].le+tr[u].ri)>>1;
    int imx=INT_MIN;
    if(le<=mid) imx=query(u<<1,le,ri);
    if(ri>mid) imx=max(imx,query(u<<1|1,le,ri));

    return imx;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>m;
    for(int i=1; i<=n; i++) {
        cin>>a[i];
    }
    build(1,1,n);

    int le,ri;
    while(m--) {
        cin>>le>>ri;
        cout<<query(1,le,ri)<<"\n";
    }
}

/*
in:
10 2
3 2 4 5 6 8 1 2 9 7
1 4
3 8

out:
5
8
*/

【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/120479214
https://www.acwing.com/solution/content/131223/
https://blog.csdn.net/hnjzsyjyj/article/details/157292085


 

​