Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

Re:给一个线段树容易出错的测试用例

Posted by black_sky_zhang at 2016-07-28 11:53:19 on Problem 3468
In Reply To:给一个线段树容易出错的测试用例 Posted by:fanlonglong8500 at 2008-08-25 10:54:41
```#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));
}
}```

Followed by: