RMQ问题

RMQ (Range Minimum/Maximum Query)问题就是区间最大最小问题。我总结了一下,这实际上也是线段树能解决的问题。

RMQ问题使用ST(Sparse Table)表,即稀疏表算法来解决。但是稀疏表比线段数好在哪里呢??稀疏表的查询时间复杂度为O(1)O(1)!而且经过

先把RMQ通过笛卡尔树变成LCA,然后通过欧拉序列把LCA变成±RMQ,然后再通过一个什么分块的table在O(n)-O(1)时间内解决。

后可以将预处理时间降到O(n)。当然这十分的麻烦,一般用不上。

稀疏表的构建

稀疏表是动态规划思想的应用。设fi,jf_{i,j}为从第i个元素开始的2j2^j个元素即区间[i,i+2j1][i,i+2^j-1]的最小值。那么很容易根据定义得到状态转移方程:

fi,j=min/max{fi,j1,fi+2j,j1}f_{i,j}=min/max\{f_{i,j-1},f_{i+2^j,j-1}\}

稀疏表状态转移方程

每次写出这个状态转移方程,就长吁一口气,感觉这个动规问题已经做完了。

但是!对于这个问题还没有。

稀疏表的查询

对于每一个查询[l,r][l,r]的最值,寻找最大的整数k,使得2krl+12^k\leq r-l+1。这个运算可以化简为取对数运算。这样的k取出来了之后,我们一定会有2krl+122k2^k\leq r-l+1 \leq 2*2^k.查询的结果就为

query(l,r)=min/max{fl,k,fr2k+1,k}query(l,r)=min/max\{f_{l,k},f_{r-2^k+1,k}\}

稀疏表查询

发现下面两个绿色的东西事实上已经被预处理过了。O(1)O(1)解决查询问题!

拉一道例题来做一做

UVa11235:

非常贴心啊… “A naive program”将不会在规定时间内完成。

我想了一个大概的思路……因为元素是排好序的,所以我们可以把这个数组压缩成(数字,个数)的形式,储存各种乱七八糟的指针。对于每一个查询[l,r],分为三部分:l右边的相同数字,r左边的相同数字,以及中间的数字。中间的数字可以使用稀疏表来存储,左右两边使用指针储存每一个数字的左端点和右端点,计算出来就好。

我AC了之后没有保存代码!万恶的UVA不仅访问速度慢,而且还不保存代码!

我只得自己重新敲一遍……

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#define MAXN 100010
using namespace std;
int n,f[MAXN][18],l[MAXN],r[MAXN],pos[MAXN],stack[MAXN],top,num[MAXN];
inline void construct(){//构造动态规划的数组
    for(int i=top-1;i>=0;i--){
        f[i][0]=stack[i];
        for(int j=1;i+(1<<j)-1<top;j++){
            f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
        }
    }
}
inline int query(int a,int b){//查询
    if(a>b){
        return 0;
    }
    int g=log(b-a+1)/log(2);//寻找最大的k
    return max(f[a][g],f[b-(1<<g)+1][g]);
}
int main(){
    int q,a,b;
    scanf("%d",&n);
    while(n){
        scanf("%d",&q);
        num[0]=-2147483647;//这里是为了保证num[0]!=num[1]
        top=0;
        for(int i=1;i<=n;i++){
            scanf("%d",&num[i]);
            if(num[i]==num[i-1]){
                stack[top-1]++;
                r[top-1]=i;
                pos[i]=top-1;
            }else{
                l[top]=r[top]=i;
                stack[top]=1;
                pos[i]=top;
                top++;
            }
        }
        construct();
        while(q--){
            scanf("%d%d",&a,&b);
            printf("%d\n",max(
                max(
                    (r[pos[a]]>b?b:r[pos[a]])-a+1,
                    b-(l[pos[b]]<a?a:l[pos[b]])+1
                ),
                query(pos[a]+1,pos[b]-1)
            ));
        }
        scanf("%d",&n);
    }
}

终于搞定了……

avatar
Kerry Su