Balanced Lineup---poj3264线段树基础

时间:2021-02-22 07:14:15

题目链接

求对应区间最大值与最小值的差;

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#define INF 0xfffffff
#define N 50010
using namespace std; #define Lson r<<1
#define Rson r<<1|1 struct SegTree
{
int L, R, Min, Max;
int mid()
{
return (L+R)>>;
}
}a[N*];
int MIN,MAX;
void BuildSegTree(int r, int L, int R)
{
a[r].L = L, a[r].R = R;
if(L == R)
{
scanf("%d", &a[r].Max);
a[r].Min = a[r].Max;
return;
}
BuildSegTree(Lson, L, a[r].mid());
BuildSegTree(Rson, a[r].mid()+, R); a[r].Max = max(a[Rson].Max, a[Lson].Max);
a[r].Min = min(a[Rson].Min, a[Lson].Min);
// a[r].ans = a[r].Max - a[r].Min;
}
void Query(int r, int L, int R)
{
if(a[r].L == L && a[r].R == R)
{
MAX=max(MAX, a[r].Max);
MIN=min(MIN, a[r].Min);
return ;
}
if(L>a[r].mid())
Query(Rson, L ,R);
else if(R <= a[r].mid())
Query(Lson, L, R);
else
{
Query(Lson, L, a[r].mid());
Query(Rson, a[r].mid()+, R);
}
}
int main()
{
int n, m, L, R;
while(scanf("%d%d", &n, &m) != EOF)
{
BuildSegTree(, , n);
while(m--)
{
MIN=INF;
MAX=-;
scanf("%d%d", &L,&R);
Query(, L, R);
printf("%d\n", MAX-MIN);
}
}
return ;
}