Posted on 2011-11-28 17:02
C小加 閱讀(1548)
評論(0) 編輯 收藏 引用 所屬分類:
解題報告
題意：給出一組數(shù)，輸出區(qū)間最大值和最小值的差值
思路：線段樹水題。建樹的時候直接把最值初始化好，然后直接找最值。1700+ms
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
inline int L(int r){return r<<1;}
inline int R(int r){return (r<<1)+1;}
inline int MID(int l,int r){return (l+r)>>1;}
const int MAXN=50003;
const int INF=0x7fffffff-1;
int ansmax,ansmin;
typedef struct
{
int left,right;
int _max,_min;
}Node;
Node tree[MAXN*4];
int arr[MAXN];
void Create(int l,int r,int root)
{
tree[root].left=l;
tree[root].right=r;
if(l==r)
{
tree[root]._max=arr[l];
tree[root]._min=arr[l];
return;
}
int mid=MID(l,r);
Create(l,mid,L(root));
Create(mid+1,r,R(root));
tree[root]._max=max(tree[L(root)]._max,tree[R(root)]._max);
tree[root]._min=min(tree[L(root)]._min,tree[R(root)]._min);
}
void Solve(int l,int r,int root)
{
if(tree[root].left==l&&tree[root].right==r)
{
ansmax=max(ansmax,tree[root]._max);
ansmin=min(ansmin,tree[root]._min);
return;
}
if(tree[root].left==tree[root].right) return;
int mid=MID(tree[root].left,tree[root].right);
if(l>mid) Solve(l,r,R(root));
else if(r<=mid) Solve(l,r,L(root));
else
{
Solve(l,mid,L(root));
Solve(mid+1,r,R(root));
}
}
int main()
{
int m,n;
while(scanf("%d %d",&m,&n)!=EOF)
{
for(int i=1;i<=m;i++)
{
scanf("%d",arr+i);
}
Create(1,m,1);
int tl,tr;
while(n--)
{
ansmax=0;
ansmin=INF;
scanf("%d %d",&tl,&tr);
if(tl==tr)
{
printf("0\n");
continue;
}
Solve(tl,tr,1);
printf("%d\n",ansmax-ansmin);
}
}
return 0;
}