UESTC 1591 An easy problem A ST表、简单题

An easy problem A ST表、简单题

Source

2017 UESTC Training for Data Structures

UESTC 1591 An easy problem A

My Solution

题意：每次查询区间内极差。

ST表、简单题
可以用2个ST表，分别维护区间最大值和区间最小值
先O(nlogn)的预处理出来，
然后每次O(1)的查询，
每次的极差即为 区间最大值 - 区间最小值
复杂度 O(nlogn)

#include 
#include 

using namespace std;


const int MAXN = 1e5 + 8;
int arr[MAXN];
struct ST_list{
    int stTable[MAXN][32], preLog2[MAXN];
    inline void st_prepare(const int &n, int arr[], const int &f){
        preLog2[1] = 0;
        for(int i = 2; i <= n; i++){
            preLog2[i] = preLog2[i-1];
            if((1 << (preLog2[i] + 1)) == i){ preLog2[i]++; } } for(int i = n - 1; i >= 0; i--){
            stTable[i][0] = arr[i];
            for(int j = 1; (i + (1 << j) - 1) < n; j++){
                if(f)stTable[i][j] = min(stTable[i][j - 1], stTable[i + (1 << j - 1)][j - 1]);
                else stTable[i][j] = max(stTable[i][j - 1], stTable[i + (1 << j - 1)][j - 1]);
            }
        }
    }

    inline int query_min(const int &l, const int &r, const int &f){
        int len = r - l + 1, k = preLog2[len];
        return f ? min(stTable[l][k], stTable[r - (1 << k) + 1][k]) : max(stTable[l][k], stTable[r - (1 << k) + 1][k]); } }sta, stb; //!为什么其它题都可以用 ios::sync_with_stdio(false); cin.tie(0); 来加快io流， 但数据结构专题去被禁止了 int main() { #ifdef LOCAL freopen("a.txt", "r", stdin); //freopen("b.out", "w", stdout); #endif // LOCAL //ios::sync_with_stdio(false); cin.tie(0); int n, q, l, r; //cin >> n >> q;
    scanf("%d%d", &n, &q);
    //! 1 ~ n based
    for(int i = 1; i <= n; i++){ cin >> arr[i];
    }
    sta.st_prepare(n+1, arr, 1);
    stb.st_prepare(n+1, arr, 0);
    for(int i = 0; i < q; i++){
        scanf("%d%d", &l, &r);
        printf("%dn", stb.query_min(l, r, 0) - sta.query_min(l, r, 1) );
    }

    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx