题目描述

每天，农夫 John 的 N头牛总是按同一序列排队。
有一天，John 决定让一些牛玩一场飞盘比赛。
他准备找一群在队列中位置连续的牛来进行比赛，但是为了避免水平悬殊，牛的身高不应该相差太大。
John 准备了 Q个可能的牛的选择和所有牛的身高。
他想知道每一组里面最高和最矮的牛的身高差别。

样例

INPUT
6 3
1
7
3
4
2
5
1 5
4 6
2 2
OUTPUT
6
3
0

算法1

(暴力枚举) $O(区间长度)$

打擂台即可。

C++ 代码

咕咕咕

算法2

(线段树) $O(log区间长度)$

构造一棵线段树，每一个节点记录[l,r]的最大值与最小值。在查询时如果遇到完整的区间就可以直接查询，降低时间消耗。本题涉及线段树的建树与区间查询，不会的可以自行学习。

参考文献

关于数据结构（线段树）的算法书或文章。

C++ 代码

#include <bits/stdc++.h>
#define RE register int
using namespace std;

int a[50010], mn[200010], mx[200010];

int lc(int p){
    return p << 1;
}

int rc(int p){
    return p << 1 | 1;
}

void pushup(int p){
    mx[p] = max(mx[lc(p)], mx[rc(p)]);
    mn[p] = min(mn[lc(p)], mn[rc(p)]);
}

void bulid(int p, int l, int r){
    if (l == r){
        mx[p] = a[l];
        mn[p] = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    bulid(lc(p), l, mid);
    bulid(rc(p), mid + 1, r);
    pushup(p);
}

int getmn(int L, int R, int p, int l, int r){
    if (L <= l && r <= R){
        return mn[p];
    }
    int mid = (l + r) >> 1;
    int ans = INT_MAX;
    if (L <= mid) ans = min(ans, getmn(L, R, lc(p), l, mid));
    if (R >= mid + 1) ans = min(ans, getmn(L, R, rc(p), mid + 1, r));
    return ans;
}

int getmx(int L, int R, int p, int l, int r){
    if (L <= l && r <= R){
        return mx[p];
    }
    int mid = (l + r) >> 1;
    int ans = INT_MIN;
    if (L <= mid) ans = max(ans, getmx(L, R, lc(p), l, mid));
    if (R >= mid + 1) ans = max(ans, getmx(L, R, rc(p), mid + 1, r));
    return ans;
}


int main(){
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
    }
    bulid(1, 1, n);
    for (int i = 1; i <= q; i++){
        int l, r;
        cin >> l >> r;
        cout << getmx(l, r, 1, 1, n) - getmn(l, r, 1, 1, n) << endl;
    }
    return 0;
}

当然此题正解是ST表，敲完暴力数据结构之后也可以学习一下倍增思想的ST表。