P1816 忠诚

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const ll N=100100;
 5 ll minn[N<<2];
 6 ll a[N];
 7 ll n,m;
 8 ll cnt;
 9 void build(ll rt,ll l,ll r){
10     if(l==r){
11         ++cnt;
12         minn[rt]=a[cnt];
13         //return ;
14     }else {
15         ll mid = (l+r)>>1;
16         build(rt*2,l,mid);
17         build(rt*2+1,mid+1,r);
18         minn[rt]=min(minn[rt*2],minn[rt*2+1]);
19     }
20     //return ;
21 }
22 
23 ll get(ll rt,ll l,ll r,ll zuo,ll you){
24     ll ans=1e8;
25     if(zuo<=l&&you>=r){
26         return ans=minn[rt];
27     } else {
28         ll mid = (l+r)>>1;
29         if(zuo<=mid){
30             ans=min(ans,get(rt*2,l,mid,zuo,you));
31         }
32         if(you>mid){
33             ans=min(ans,get(rt*2+1,mid+1,r,zuo,you));
34         }
35     }
36     return ans;
37 }
38 
39 int main(){
40     scanf("%lld%lld",&n,&m);
41     for(ll i=1;i<=n;i++){
42         scanf("%lld",&a[i]);
43     }
44     build(1,1,n);
45     for(ll i=1;i<=m;i++){
46         ll a,b;
47         scanf("%lld%lld",&a,&b);
48         printf("%lld ",get(1,1,n,a,b));
49     }
50     return 0;
51 }