记录编号	426676	评测结果	AAAAAAAAAA
题目名称	忠诚	最终得分	100
用户昵称	kZime	是否通过	通过
代码语言	C++	运行时间	1.375 s
提交时间	2017-07-18 16:48:12	内存使用	0.70 MiB

# include <bits/stdc++.h>
# define INF 0x7fffffff
# define mid ((l + r) >> 1)
using namespace std;

struct node  {
    int mi;
    node *ls, *rs;
    node() {mi = INF;}
    inline void pu() { 
        mi = min((ls) ? ls->mi : INF, (rs) ? (rs->mi) : INF);
    }
}*root;

int a[100002];

node *build(int l, int r) { 
    node *x = new node();
    if(l ^ r) { 
        x->ls = build(l, mid);
        x->rs = build(mid + 1, r);
        x->pu();
    } else { 
        x->mi = a[l];
    }
    return x;
}

int query(node *x, int l, int r, int s, int t) { 
    if(l != s || r != t) { 
        if(t <= mid) return query(x->ls, l, mid, s, t);
        else if(s > mid)return query(x->rs, mid + 1, r, s, t);
        else return min(query(x->ls, l, mid, s, mid), query(x->rs, mid + 1, r, mid + 1, t));
    } else { 
        return x->mi;
    }
}

int main() { 
    freopen("faithful.in", "r", stdin);
	freopen("faithful.out", "w", stdout);
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++) { 
        cin >> a[i];
    }
    root = build(1, n);
    for(int i = 1; i <= m; i++) { 
        int l, r;
        cin >> l >> r;
        cout << query(root, 1, n, l, r);
    }
}