poj 3264 Balanced Lineup(線分ツリー単点修正区間クエリー)

タイトルリンク:クリックしてリンクを開く
セグメントツリーの単一点修正区間クエリー
各ノードに最大値と最小値を保存
コード:

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define M 50010
#define inf 10000000
int MIN[M<<2];
int MAX[M<<2];
void pushup(int rt){
    MIN[rt]=min(MIN[rt<<1],MIN[rt<<1|1]);
    MAX[rt]=max(MAX[rt<<1],MAX[rt<<1|1]);
}

void build(int l,int r,int rt){
    MIN[rt]=inf;
    MAX[rt]=0;
    if(l==r) return;
    int m=(l+r)>>1;
    build(lson);
    build(rson);
}

void update(int l,int r,int rt,int p,int d){
    MIN[rt]=min(d,MIN[rt]);
    MAX[rt]=max(d,MAX[rt]);
    if(l==r) return ;
    int m=(l+r)>>1;
    if(m>=p) update(lson,p,d);
    else update(rson,p,d);
    pushup(rt);
}

int querymax(int L,int R,int l,int r,int rt){
    if(L<=l&&R>=r)return MAX[rt];
    int m=(l+r)>>1;
    int res=0;
    if(m>=L) res=max(res,querymax(L,R,lson));
    if(m<R) res=max(res,querymax(L,R,rson));
    return res;
}

int querymin(int L,int R,int l,int r,int rt){
    if(L<=l&&R>=r)return MIN[rt];
    int m=(l+r)>>1;
    int res=inf;
    if(m>=L) res=min(res,querymin(L,R,lson));
    if(m<R) res=min(res,querymin(L,R,rson));
    return res;
}

int main(){
    int N,Q;
    while(~scanf("%d%d",&N,&Q)){
        build(1,N,1);
        for(int i=1;i<=N;i++){
            int t;
            scanf("%d",&t);
            update(1,N,1,i,t);
        }
        for(int i=1;i<=Q;i++){
            int s,t;
            scanf("%d%d",&s,&t);
            cout<<querymax(s,t,1,N,1)-querymin(s,t,1,N,1)<<endl;
        }
    }
    return 0;
}