COCR#1 T4-定点の轰炸

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct SegNode{
    int maxHIdx;
};
void build(vector<int>& hts,vector<SegNode>& tr,int nd,int st,int ed){
    if(st==ed){
        tr[nd].maxHIdx=st;
        return;
    }
    int mid=(st+ed)/2;
    int lc=2*nd+1;
    int rc=2*nd+2;
    build(hts,tr,lc,st,mid);
    build(hts,tr,rc,mid+1,ed);
    if (hts[tr[lc].maxHIdx]>hts[tr[rc].maxHIdx]){
        tr[nd].maxHIdx=tr[lc].maxHIdx;
    }else if(hts[tr[lc].maxHIdx]<hts[tr[rc].maxHIdx]){
        tr[nd].maxHIdx=tr[rc].maxHIdx;
    }else{
        tr[nd].maxHIdx=min(tr[lc].maxHIdx, tr[rc].maxHIdx);
    }
}
int query(vector<int>& hts,vector<SegNode>& tr,int nd,int st,int ed,int l,int r){
    if(l>ed||r<st){
        return -1;
    }
    if(l<=st&&r>=ed){
        return tr[nd].maxHIdx;
    }
    int mid=(st+ed)/2;
    int lc=2*nd+1,rc=2*nd+2;
    int lr=query(hts,tr,lc,st,mid,l,r),rr=query(hts,tr,rc,mid+1,ed,l,r);
    if(lr==-1){
        return rr;
    }
    if(rr==-1){
        return lr;
    }
    if(hts[lr]>hts[rr]){
        return lr;
    }else if(hts[lr]<hts[rr]){
        return rr;
    }else{
        return min(lr,rr);
    }
}
int main() {
    int N,Q;
    cin>>N>>Q;
    vector<int>hts(N);
    for(int i=0;i<N;++i){
        cin>>hts[i];
    }
    vector<SegNode>tr(4*N);
    build(hts,tr,0,0,N-1);
    for(int i=0;i<Q;++i){
        int l,r;
        cin>>l>>r;
        l--;
        r--;
        int res=query(hts,tr,0,0, N-1,l,r);
        cout<<res+1<<endl;
    }
    return 0;
}