poj 3264 Balanced Lineup(線分ツリー単点修正区間クエリー)
1803 ワード
タイトルリンク:クリックしてリンクを開く
セグメントツリーの単一点修正区間クエリー
各ノードに最大値と最小値を保存
コード:
セグメントツリーの単一点修正区間クエリー
各ノードに最大値と最小値を保存
コード:
#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;
}