Visit Counter
AmazingCounters.com

1、题目大意:给一个序列,给一些询问,求区间最大值和最小值
2、分析: 懒得脑补st表 ,直接线段树裸上
3、代码:

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
int qmin[200010], qmax[200010]; 
int a[200010];
int getint(){
    char ch = getchar(); int x = 0, f = 1;
    while(ch < '0' || ch > '9'){
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while('0' <= ch && ch <= '9'){
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
inline void build(int l, int r, int o){
    if(l == r){
        qmin[o] = qmax[o] = a[l];
        return;
    }
    int mid = (l + r) / 2;
    build(l, mid, 2 * o);
    build(mid + 1, r, 2 * o + 1);
    qmin[o] = min(qmin[2 * o], qmin[2 * o + 1]);
    qmax[o] = max(qmax[2 * o], qmax[2 * o + 1]);
    return; 
}
inline int query_min(int l, int r, int o, int x, int y){
    if(x <= l && r <= y){
        return qmin[o];
    }
    int mid = (l + r) / 2;
    int res = 2147483647;
    if(x <= mid) res = min(res, query_min(l, mid, 2 * o, x, y));
    if(y > mid) res = min(res, query_min(mid + 1, r, 2 * o + 1, x, y));
    return res;
}
inline int query_max(int l, int r, int o, int x, int y){
    if(x <= l && r <= y){
        return qmax[o];
    }
    int mid = (l + r) / 2;
    int res = 0;
    if(x <= mid) res = max(res, query_max(l, mid, 2 * o, x, y));
    if(y > mid) res = max(res, query_max(mid + 1, r, 2 * o + 1, x, y));
    return res;
}
int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
    build(1, n, 1);
    for(int i = 1; i <= m; i ++){
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", query_max(1, n, 1, l, r) - query_min(1, n, 1, l, r));
    }
    return 0;
}