balanced lineup(线段树).cpp

杭电acm解题报告2001---2099.

#include <cstdio>
#include <string>
#define MAX 50100

int n,q;
int cow[MAX];

struct node {
	node * pleft,* pright;
	int left,right;
	int mmax;
	int mmin;
};
node mem[200000];
int mem_pos;

node * new_node() 
{
	node * p = &mem[mem_pos ++ ];
	memset(p,0,sizeof(node));
	return p;
}

node * make_tree(int x,int y)
{
	int mid = (x+y)/2;
	node * root = new_node();

	root ->left = x;
	root ->right = y;
	
	if (y - x <= 1) {
		root ->mmax = cow[x] > cow[y] ? cow[x] : cow[y];
		root ->mmin = cow[x] < cow[y] ? cow[x] : cow[y];
	}
	else {
		root ->pleft = make_tree(x,mid);	
		root ->pright = make_tree(mid,y);
		node * pl = root ->pleft;
		node * pr = root ->pright;
		root ->mmax = pl ->mmax > pr ->mmax ? pl ->mmax : pr ->mmax;
		root ->mmin = pl ->mmin < pr ->mmin ? pl ->mmin : pr ->mmin;
	}

	return root;
}

int get_max(node * root,int x,int y)
{
	if (x == root ->left && y == root ->right) {
		return root ->mmax;
	}
	int mid = (root ->left + root ->right)/2;
	if (x >= mid) {
		return get_max(root ->pright,x,y);
	}
	if (y <= mid) {
		return get_max(root ->pleft,x,y);
	}
	int max1 = get_max(root ->pleft,x,mid);
	int max2 = get_max(root ->pright,mid,y);
	return max1 > max2 ? max1 : max2;
}

int get_min(node * root,int x,int y)
{
	if (x == root ->left && y == root ->right) {
		return root ->mmin;
	}
	int mid = (root ->left + root ->right)/2;
	if (x >= mid) {
		return get_min(root ->pright,x,y);
	}
	if (y <= mid) {
		return get_min(root ->pleft,x,y);
	}
	int min1 = get_min(root ->pleft,x,mid);
	int min2 = get_min(root ->pright,mid,y);
	return min1 < min2 ? min1 : min2;
}

int main()
{
	int i,x,y;
	int mmax,mmin;
	node * root;

	while (scanf("%d %d",&n,&q) == 2 ) {
		mem_pos = 0;
		for(i=1;i<=n;i++) {
			scanf("%d",&cow[i]);
		}
		root = make_tree(1,n);
		while (q--) {
			scanf("%d %d",&x,&y);
			if( x == y ) {
				printf("0\n");
			}
			else {
				mmax = get_max(root,x,y);
				mmin = get_min(root,x,y);
				printf("%d\n",mmax - mmin);
			}
		}
	}
}