线段树求区间最值
http://acm.njupt.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1042
#include<iostream> #include<algorithm> #include<stdio.h> using namespace std; #define MAX 10002 struct node{ int l,r,min; }tree[MAX*4]; int e[MAX];int n;int MIN; int min(int a,int b){ return a>b?b:a; } void build(int root,int l,int r){ tree[root].l=l;tree[root].r=r; if(l==r){ tree[root].min=e[l]; return; } int mid=(l+r)/2; build(2*root,l,mid); build(2*root+1,mid+1,r); tree[root].min=min(tree[root*2].min,tree[2*root+1].min); } void query(int root,int l,int r){ if(tree[root].l==l && tree[root].r==r){ if(MIN>tree[root].min)MIN=tree[root].min; return; } int mid=(tree[root].l+tree[root].r)/2; if(mid>=r)query(2*root,l,r); else if(mid<l)query(2*root+1,l,r); else { query(root*2,l,mid); query(root*2+1,mid+1,r); } } int main(int argc, char *argv[]) { scanf("%d",&n);int q;int l,r; for(int i=1;i<=n;++i) scanf("%d",e+i); build(1,1,n); scanf("%d",&q); for(int i=0;i<q;++i){ MIN=999999999; scanf("%d%d",&l,&r); query(1,l,r); cout<<MIN<<endl; } return 0; }
