TIOJ 1603 胖胖殺蚯事件 [ RMQ ]

73346    poao899    5088K    374MS    G++     1.43K     2010-04-02 11:24:19                                       .


SKYLY: 想當年第一次出現這個大家都不會沒想到現在已經平民化了




試寫Segment Tree.


//**********************************************

#include<stdio.h>
unsigned  val[100010], n, q, a, b;
struct seg{
	unsigned l, r, v1, v2;
	seg *lch, *rch;
	unsigned max(unsigned,unsigned);
	unsigned min(unsigned,unsigned);
}s[300000];
seg *get(unsigned l, unsigned r){
	static int cnt=0;
	s[cnt].l=l; s[cnt].r=r; s[cnt].v1=0; s[cnt].v2=222222222u;
	return s+cnt++;
}
unsigned seg::max(unsigned _l, unsigned _r){
	//printf(">>%u %u\n",l,r);
	if(l== r)return v1= val[l];
	unsigned m1, m2, mid=(l+r)/2;
	if(!lch){
		lch= get(l, mid);
		rch= get(mid+1, r);
	}
	if(_l==l&& _r==r){
		if(!v1){
			m1= lch->max(l, mid);
			m2= rch->max(mid+1, r);
			v1= m1>m2?m1:m2;
		}return v1;
	}
	if(_l> mid)
		return rch->max(_l, _r);
	else if(_r<= mid)
		return lch->max(_l, _r);
	else{
		m1= lch->max(_l, mid);
		m2= rch->max(mid+1, _r);
		return m1>m2?m1:m2;
	}
}
unsigned seg::min(unsigned _l, unsigned _r){
	if(l== r)return v2= val[l];
	unsigned m1, m2, mid=(l+r)/2;
	if(_l==l&& _r==r){
		if(v2==222222222u){
			m1= lch->min(l, mid);
			m2= rch->min(mid+1, r);
			v2= m1<m2?m1:m2;
		}return v2;
	}
	if(_l> mid)
		return rch->min(_l, _r);
	else if(_r<= mid)
		return lch->min(_l, _r);
	else{
		m1= lch->min(_l, mid);
		m2= rch->min(mid+1, _r);
		return m1<m2?m1:m2;
	}
}
int main(){
	scanf("%u %u", &n, &q);
	for(int i=1; i<=n; i++)
		scanf("%u", val+i);
	get(1, n);
	while(q--){
		scanf("%u%u", &a, &b);;
		printf("%u\n", s[0].max(a,b)-s[0].min(a,b));
	}
}