RMQ问题 - ST表的简单应用

2017-08-26 22:25:57

writer：pprp

题意很简单，给你一串数字，问你给定区间中最大值减去给定区间中的最小值是多少？

用ST表即可实现

一开始无脑套模板，找了最大值，找了最小值，分别用两个函数实现，实际上十分冗余

所以TLE了

之后改成一个函数中同时处理最大值和最小值，就可以了

AC代码如下：

/*

@theme:poj 3264

@writer:pprp

@declare:ST表（sparse table）稀疏表,用动态规划的思想来解决RMQ问题；

@date:2017/8/26

*/

//#include <bits/stdc++.h>

#include <iostream>

#include <cmath>

#include <cstdio>

#include <cstdlib>

#define IOS ios::sync_with_stdio(false),cin.tie(0);

using namespace std;

const int maxn = ;

int F1[maxn][];

int F2[maxn][];

int a[maxn];

void SparseTable(int a[], int len)

{

    //初始化

    for(int i =  ; i < len ; i++)

    {

        F1[i][] = a[i];

        F2[i][] = a[i];

    }

    //递推

    //找到j的范围log2(n)

    int nlog = int(log(double(len))/log(2.0));

    for(int j =  ; j <= nlog; j++)

    {

        for(int i =  ; i < len ; i++)

        {

            //区间右端点不能超过数组最后一位下标

            if((i + ( << j) -) < len )

            {

                F1[i][j] = min(F1[i][j - ],F1[i + ( << (j - ))][j - ]);

                F2[i][j] = max(F2[i][j - ],F2[i + ( << (j - ))][j - ]);

            }

        }

    }

}

int main()

{

    int N, Q;

    int l, r;

    scanf("%d %d",&N,&Q);

    for(int i =  ; i < N ; i++)

    {

        scanf("%d",&a[i]);

    }

    SparseTable(a,N);

    for(int i =  ; i < Q ; i++)

    {

        scanf("%d %d",&l,&r);

        l--;

        r--;

        double len = r - l + ;

        int m = (int)(log(len)/log(2.0));

        int mmx = max(F2[l][m],F2[r-(<<m)+][m]);

        int mmn = min(F1[l][m],F1[r-(<<m)+][m]);

        printf("%d\n",mmx-mmn);

    }

    return ;

}