poj 3264 Balanced Lineup[線分樹,,水]
1474 ワード
区間の中で最も値の差を求めます.
2つのクエリーを使用しました.時間3 S+...とても遅くて、、高速のアルゴリズムを求めます
2つのクエリーを使用しました.時間3 S+...とても遅くて、、高速のアルゴリズムを求めます
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int MM=1000005;
const int maxn=50005;
int MAX[maxn<<2],MIN[maxn<<2];
void build(int l,int r,int rt){
if(l==r){
scanf("%d",&MAX[rt]);
MIN[rt]=MAX[rt];
return ;
}
int m=(l+r)>>1;
build(lson);
build(rson);
MAX[rt]=max(MAX[rt<<1],MAX[rt<<1|1]);
MIN[rt]=min(MIN[rt<<1],MIN[rt<<1|1]);
}
int query1(int L,int R,int l,int r,int rt){
if(L<=l&&R>=r){
return MAX[rt];
}
int m=(l+r)>>1;
int ret=0;
if(L<=m) ret=max(ret,query1(L,R,lson));
if(R>m) ret=max(ret,query1(L,R,rson));
return ret;
}
int query2(int L,int R,int l,int r,int rt){
if(L<=l&&R>=r){
return MIN[rt];
}
int m=(l+r)>>1;
int ret=MM;
if(L<=m) ret=min(ret,query2(L,R,lson));
if(R>m) ret=min(ret,query2(L,R,rson));
return ret;
}
int main() {
int N,Q;
while(~scanf("%d%d",&N,&Q)) {
build(1,N,1);
while(Q--){
int a,b;
scanf("%d%d",&a,&b);
printf("%d
",query1(a,b,1,N,1)-query2(a,b,1,N,1));
}
}
return 0;
}