POJ 3264 Balanced Lineup 线段树RMQ

题目大意：

给定N个数，还有Q个询问，求每个询问中给定的区间[a,b]中最大值和最小值之差。

思路：

依旧是线段树水题~

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int MAXN=50000+10;

const int MAXM=MAXN<<2;

const int INF=0x3fffffff;

int maxv[MAXM],minv[MAXM],a[MAXN];

void build(int k,int L,int R)

{

	if(L==R)

	{

		maxv[k]=a[L];

		minv[k]=a[L];

	}

	else

	{

		int m=(L+R)>>1;

		build(k<<1,L,m);

		build((k<<1)+1,m+1,R);

		maxv[k]=max(maxv[k<<1],maxv[(k<<1)+1]);

		minv[k]=min(minv[k<<1],minv[(k<<1)+1]);

	}

}

int query_max(int k,int L,int R,int a,int b)

{

	int ans=-INF;

	if(a<=L && R<=b) return maxv[k];

	else

	{

		int m=(L+R)>>1;

		if(a<=m) ans=max(ans,query_max(k<<1,L,m,a,b));

	    if(m<b)   ans=max(ans,query_max((k<<1)+1,m+1,R,a,b));

		return ans;

 	}

}

int query_min(int k,int L,int R,int a,int b)

{

	int ans=INF;

	if(a<=L && R<=b) return minv[k];

	else

	{

		int m=(L+R)>>1;

		if(a<=m) ans=min(ans,query_min(k<<1,L,m,a,b));

		if(m<b)  ans=min(ans,query_min((k<<1)+1,m+1,R,a,b));

		return ans;

 	}

}

int main()

{

	int n,q;

	while(~scanf("%d%d",&n,&q))

	{

		for(int i=1;i<=n;i++)

			scanf("%d",&a[i]);

		build(1,1,n);

		for(int i=0;i<q;i++)

		{

			int a,b;

			scanf("%d%d",&a,&b);

			printf("%d\n",query_max(1,1,n,a,b)-query_min(1,1,n,a,b));

		}

	}

	return 0;

}

巴特西

POJ 3264 Balanced Lineup 线段树RMQ

最新文章

热门文章