POJ 3264

• 线段树每个节点区间中区间上的最大值和最小值
• 询问时找到符合的区间,不符合就二分,然后更新合并区间的最大最小值

  #include <iostream>
  #include <string.h>
  #include <algorithm>
  using namespace std;
  const int maxn = 5e4+5;
  struct segementTree {
  	int left, right;
  	int maxh, minh;
  	#define left(x) tree[x].left
  	#define right(x) tree[x].right
  	#define maxh(x) tree[x].maxh
  	#define minh(x) tree[x].minh
  }tree[4*maxn];
  int num[maxn];
  int n, m;
  struct node {
  	int one, two;
  	node(){}
  	node(int a,int b) {
  		one = a; two = b;
  	}
  };
  void build(int p,int left,int right) {
  	left(p) = left; right(p) = right;
  	if (left == right) {
  		maxh(p) = minh(p) = num[left];
  		return;
  	}
  	int mid = (left + right) / 2;
  	build(2*p,left,mid);
  	build(2*p+1,mid+1,right);
  	maxh(p) = max(maxh(p*2),maxh(p*2+1));
  	minh(p) = min(minh(p*2),minh(p*2+1));
  }
  node ask(int p,int left,int right) {
  	if (left == left(p) && right == right(p)) 
  		return node(minh(p),maxh(p));
  	int mid = (left(p) + right(p)) / 2;
  	node ans;
  	if (right <= mid) {
  		ans = ask(2*p,left,right);
  	} else if (left > mid) {
  		ans = ask(2*p+1,left,right);
  	} else {
  		node temp1 = ask(2*p, left, mid);
  		node temp2 = ask(2*p+1,mid+1,right);
  		ans.one = min(temp1.one,temp2.one);
  		ans.two = max(temp1.two,temp2.two);
  	}
  	return ans;
  }
  
  
  int main() {
  //	freopen("a.txt","r",stdin);
  	scanf("%d%d",&n,&m);
  	for (int i = 1; i <= n; i++) 
  		scanf("%d",num+i);
  	build(1,1,n);
  	int u, v;
  	for (int i = 1; i <= m; i++) {
  		scanf("%d%d",&u,&v);
  		node ans = ask(1,u,v);
  		printf("%d\n",ans.two - ans.one);
  	}
  	return 0;
  }