题目链接:
题意:
题解:
区间查询最小值
代码:
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 #define MS(a) memset(a,0,sizeof(a)) 5 #define MP make_pair 6 #define PB push_back 7 const int INF = 0x3f3f3f3f; 8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL; 9 inline ll read(){ 10 ll x=0,f=1;char ch=getchar(); 11 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 12 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 13 return x*f; 14 } 15 ////////////////////////////////////////////////////////////////////////// 16 const int maxn = 1e5+10; 17 18 int a[maxn],ans[maxn]; 19 struct node{ 20 int l,r,minn; 21 }tree[maxn<<2]; 22 23 void pushup(int rt){ 24 tree[rt].minn = min(tree[rt<<1].minn,tree[rt<<1|1].minn); 25 } 26 27 void build(int rt,int l,int r){ 28 tree[rt].l = l, tree[rt].r = r; 29 // tree[rt].minn = INF; 30 if(l == r) 31 tree[rt].minn = a[l]; 32 else{ 33 int mid = (l+r)/2; 34 build(rt<<1,l,mid); 35 build(rt<<1|1,mid+1,r); 36 pushup(rt); 37 } 38 } 39 40 int query(int rt,int l,int r){ 41 int L = tree[rt].l, R = tree[rt].r; 42 if(l<=L && R<=r) 43 return tree[rt].minn; 44 int ans = INF; 45 int mid = (L+R)/2; 46 if(l <= mid) ans = min(ans,query(rt<<1,l,r)); 47 if(r>mid) ans = min(ans,query(rt<<1|1,l,r)); 48 return ans; 49 } 50 51 int main(){ 52 int n=read(), q=read(); 53 for(int i=1; i<=n; i++) 54 a[i] = read(); 55 build(1,1,n); 56 int cnt = 0; 57 for(int i=0; i<q; i++){ 58 int a=read(),b=read(); 59 int tmp = query(1,a,b); 60 ans[++cnt] = tmp; 61 } 62 for(int i=1; i<cnt; i++) 63 cout << ans[i] << " "; 64 cout << ans[cnt] << endl; 65 66 return 0; 67 }