AcWing 1270. 数列区间最大值

#include<iostream>
#include<climits>
#include<cstdio>
using namespace std;
const int N=1e6+10;
int a[N];
struct tree{
    int l,r;
    int sum;
}tr[4*N];
void pushup(int u)
{
    tr[u].sum=max(tr[u<<1].sum,tr[u<<1|1].sum);
}
void build(int u,int l,int r)
{
    if(l==r)tr[u]={l,r,a[r]};
    else {
        tr[u]={l,r};
        int m=(l+r)>>1;
        build(u<<1,l,m);
        build(u<<1|1,m+1,r);
        pushup(u);
    }
}
int query(int u,int l,int r)
{
    if(tr[u].l>=l&&tr[u].r<=r)return tr[u].sum;
      int m=(tr[u].r+tr[u].l)>>1;
      int mx1=INT_MIN;
      if(l<=m)mx1=max(query(u<<1,l,r),mx1);//查询的区间不能修改
      if(r>=m+1)mx1=max(query(u<<1|1,l,r),mx1);//查询的区间不能修改
      return mx1;
}
int main()
{
    int n;
    int t;
    scanf("%d%d",&n,&t);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    build(1,1,n);
    while(t--)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        printf("%d\n",query(1,l,r));
    }
}