http://web2.ck.tp.edu.tw/~step5/probdisp.php?pid=0099
這題.....線段樹,尋找區間最小值。
首先,根本神曲
#include <cstdlib>
#include <iostream>
#include <special_0099.h>
#define N 1000001
using namespace std;
using namespace futa;
int gg[4*N],man[N];
int mklist(int le,int re,int id){
if(le==re){
gg[id]=man[le];
return man[le];
}
int tmp=(re-le)/2,tmp1,tmp2;
tmp1=mklist(le,le+tmp,id*2);
tmp2=mklist(le+tmp+1,re,id*2+1);
gg[id]=(tmp1<tmp2)? tmp1:tmp2;
return gg[id];
}
int find(int a,int b,int le,int re,int id){
if(re<a||le>b)return -1;
if(a<=le&&re<=b)return gg[id];
int tmp=(re-le)/2,tmp1,tmp2;
if(le==re) return gg[id];
tmp1=find(a,b,le,le+tmp,id*2);
tmp2=find(a,b,le+tmp+1,re,id*2+1);
if(tmp1!=-1 && tmp2!=-1)return (tmp1<tmp2)? tmp1:tmp2;
else return (tmp1!=-1)? tmp1:tmp2;
}
int main(int argc,char *argv[]){
int n=init(),*p=momo_gives_you_list_of_futa(),qq=momo_tells_you_q();
for(int i=1;i<=n;i++)man[i]=*(p+i-1);
mklist(1,n,1);
pair<int,int> a;
for(int i=0;i<qq;i++){
a=momo_asks();
you_tell_momo(find(a.first+1,a.second+1,1,n,1));
}
//system("pause");
return 0;
}
沒有留言:
張貼留言