记录编号	398301	评测结果	AAAAAAAAAA
题目名称	忠诚	最终得分	100
用户昵称	JustWB	是否通过	通过
代码语言	C++	运行时间	0.212 s
提交时间	2017-04-21 21:48:31	内存使用	5.40 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,a,b,mi;
int M[100001];
struct stree
{
  int l,r;
  int mi;
  stree(){l=0;r=0;mi=0; }
}tree[411111];
void build(int l,int r,int now)
{
  int mid=(l+r)/2;
  tree[now].l=l;
  tree[now].r=r;
  if(l==r)
  {
    tree[now].mi=M[l];
    return;
  }
  build(l,mid,2*now);
  build(mid+1,r,2*now+1);
  tree[now].mi=min(tree[2*now].mi,tree[2*now+1].mi);
}
void s(int dl,int dr,int now)
{
  int mid=(tree[now].l+tree[now].r)/2;
  if(dl==tree[now].l&&dr==tree[now].r)
  {
    if(tree[now].mi<mi)mi=tree[now].mi;
    return;
  }
  if(dr<=mid)
  {
    s(dl,dr,2*now);
    return;
  }
  if(dl>mid)
  {
    s(dl,dr,2*now+1);
    return;
  }
  s(dl,mid,2*now);
  s(mid+1,dr,2*now+1);
}
int main()
{
  freopen("faithful.in","r",stdin);
  freopen("faithful.out","w",stdout);
  scanf("%d%d",&m,&n);
  for(int i=1;i<=m;i++)scanf("%d",&M[i]);
  build(1,m,1);
  for(int i=1;i<=n;i++)
  {
    scanf("%d%d",&a,&b);
    mi=0x7fffff;
    s(a,b,1);
    printf("%d ",mi);
  }
  return 0;
}