数列区间最大值

题目

输入一串数字，给你 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

分析

和线段树求和差不多，只是维护的是最大值

代码

#include<cstdio>
#include<algorithm>
using namespace std;
int n,m;
int w[100006];
struct node{
    int l,r;
    int maxv;
}aa[400006];

void pushup(int u)
{
    aa[u].maxv=max(aa[u*2].maxv,aa[u*2+1].maxv);
}

void build(int u,int l,int r)
{
    if(l==r) aa[u]={l,r,w[l]};
    else
    {
        aa[u]={l,r};
        int mid=(l+r)/2;
        build(u*2,l,mid);build(u*2+1,mid+1,r);
        pushup(u);
    }
}

int query(int u,int l,int r)
{
    if(l<=aa[u].l&&aa[u].r<=r) return aa[u].maxv;
    int mid=(aa[u].l+aa[u].r)/2;
    int maxx=-999999;
    if(l<=mid) maxx=max(maxx,query(u*2,l,r));
    if(r>mid) maxx=max(maxx,query(u*2+1,l,r));
    return maxx;
}

int main()
{
    scanf("%d%d",&n,&m);
    int a,b;
    for(int i=1;i<=n;i++) scanf("%d",&w[i]);
    build(1,1,n);
    while(m--)
    {
        scanf("%d%d",&a,&b);
        printf("%d\n",query(1,a,b));
    }
    return 0;
}