#include<cstdio>
#include<algorithm>
using namespace std;
long long tree[400010],a[100005],t,m,x,y;
int n,q,l,r;
void build(int node,int begin,int end){
	if(begin==end){
		tree[node]=a[begin];
		return;
	}
	int mid=(begin+end)/2;
	build(node<<1,begin,mid);
	build(node<<1|1,mid+1,end);
	tree[node]=min(tree[node<<1],tree[node<<1|1]);
}
long long query(int node,int begin,int end,int left,int right){
	if(begin==left&&end==right)
		return tree[node];
	int mid=(begin+end)/2;
	if(right<=mid)	return query(node<<1,begin,mid,left,right);
	else if(left>mid)	return query(node<<1|1,mid+1,end,left,right);
	else
	return (min(query(node<<1,begin,mid,left,mid),query(node<<1|1,mid+1,end,mid+1,right)));
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	build(1,1,n);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		printf("%d ",query(1,1,n,x,y));
	}
}

• Re:给一个线段树容易出错的测试用例 (1579) cyy1308947278 2016-08-26 21:35:01