洛谷P1816

线段树应用（静态查询最小值）

 

 1 #include <cstdio>
 2 #include <cstring> 
 3 #include <iostream>
 4 #include <algorithm>
 5 using namespace std;
 6 const int N = 1e5 + 5,INF = 0x7fffffff;
 7 int a[N],minn[N*4],n,m;
 8 inline int read()
 9 {
10     int x=0,w=1; char c=getchar();
11     while (c>'9' || c<'0') {if(c=='-') w=-1; c=getchar();}
12     while (c<='9' && c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}
13     return w*x;
14 }
15 void build(int o,int l,int r)
16 {        
17     if (l==r) {minn[o]=a[l]; return ;}
18     int mid= (l+r)>>1;
19     build(o<<1,l,mid);
20     build(o<<1|1,mid+1,r);
21     minn[o]=min(minn[o<<1],minn[o<<1|1]);
22 }
23 int query(int o,int l,int r,int ql,int qr)
24 {
25     if (ql<=l && qr>=r) return minn[o];
26     int mid=(l+r)>>1; int minn1=INF,minn2=INF;
27     if (ql<=mid) minn1=query(o<<1,l,mid,ql,qr);
28     if (qr>mid) minn2=query(o<<1|1,mid+1,r,ql,qr);
29     return min(minn1,minn2);
30 }
31 int main()
32 {
33     n=read(); m=read();
34     for(int i=1;i<=n;++i)
35         a[i]=read();
36     build(1,1,n);
37     while(m--)
38     {
39         int l,r;
40         l=read(); r=read();
41         cout<<query(1,1,n,l,r)<<" ";
42     }
43     cout<<endl;
44     return 0;
45 }

开始WA*10（拍了好多组数据都没问题），后来发现输出应该是一行，然后就AC了

心塞