题目描述

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

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

接下来一行为 N 个数；

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

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

数据范围
1≤N≤105,
1≤M≤106,
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

#include <iostream>

using namespace std;

const int N = 100000;
int in[N+1];
struct node{
    int leftn, rightn, maxn;
    node *left, *right;
    node(int leftn, int rightn): leftn(leftn), rightn(rightn), maxn(0), left(NULL), right(NULL){};
};

node* build(int left, int right){
    node *p = new node(left, right);
    if(left == right){
        p->maxn = in[left];
        return p;
    }

    int mid = (left+right)/2;
    p->left = build(left, mid);
    p->right = build(mid+1, right);
    p->maxn = max(p->left->maxn, p->right->maxn);

    return p;
}

int get(node *head, int x, int y){
    if(head->leftn == x && head->rightn == y) return head->maxn;

    int maxn = 0;


    if(head->left->rightn >= x && head->left->rightn >= y) maxn = max(maxn, get(head->left, x, y));
    else if(head->left->rightn >= x && head->left->rightn < y) 
        maxn = max(maxn, max(get(head->left, x, head->left->rightn), get(head->right, head->right->leftn, y)));
    else maxn = max(maxn, get(head->right, x, y));

    return maxn;
}

int main(){
    int n, m, x, y;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) scanf("%d", &in[i]);

    node *head = build(1, n);

    for(int i = 0; i < m; i++){
        scanf("%d%d", &x, &y);
        printf("%d\n", get(head, x, y));
    }
    return 0;
}