一种有趣的 O(n)-O(1) RMQ

xfrvq · 2023-01-12 19:08:53 · 个人记录

你先别急，因为不是四毛子。

算法来自：https://www.luogu.com.cn/blog/35137/solution-p3793

考虑将原序列以 \log n 为块长分块，块数为 \dfrac n{\log n} 级别。

整块答案就将每个块的最小值记录为一个新数组，然后构建 \tt ST 表，复杂度 \mathcal O(\dfrac n{\log n}\log \dfrac n{\log n})，不到 \mathcal O(n)。

先别急着散块暴力，我们尝试想一种对于长度为 30 左右的数列，做到 \mathcal O(n)-\mathcal O(1) 的 \tt RMQ 的算法。

考虑正在询问 [l,r] 的最小值，我们对 [1,r] 构建一个单调上升的单调栈。然后考虑单调栈的定义，其构造应该是：

• 最后一个元素是 a_r
• 倒数第二个元素 a_p 是 r 左边第一个 \lt a_r 的值
• 接着 a_q 是 p 左边第一个 \lt a_p 的值。
• \cdots

于是我们发现这么一点：

• \min\{a_p,\cdots,a_r\}=a_p
• \min\{a_q,\cdots,a_p\}=a_q\lt a_p
• \cdots

所以单调栈中 a_l 右边的第一个元素就是 [l,r] 的最小值。

因为序列长度 \le 30，我们考虑用 int 状压来存 每个元素是否在单调栈内，然后开一个 int[30] 用来存每个 [1,i] 的单调栈。

单调栈可以通过二进制位移做到只保留 a_l,\cdots,a_r 的元素，然后再求一个最前元素可以通过一个 二进制下最低位 函数来求，这两步是 \mathcal O(1) 的。

求最小值所在位置的实现。

namespace RMQ{
    const int Blk = 28,SIZ = N / Blk + 1;

    int bl[N],bg[SIZ],ed[SIZ];
    int pre[N],suf[N],stk[35];
    int st[17][SIZ];
    unsigned val[N];

    int cmp(int x,int y){ return a[x] < a[y] ? x : y; }

    void init(){
        for(int i = 1;i <= n;++i) pre[i] = suf[i] = i;
        int C = (n - 1) / Blk + 1;
        for(int i = 1;i <= C;++i){
            bg[i] = ed[i - 1] + 1;
            ed[i] = i != C ? bg[i] + Blk - 1 : n;
            for(int j = bg[i];j <= ed[i];++j)
                st[0][bl[j] = i] = cmp(st[0][i],j);
            for(int j = bg[i] + 1;j <= ed[i];++j)
                pre[j] = cmp(pre[j],pre[j - 1]);
            for(int j = ed[i] - 1;j >= bg[i];--j)
                suf[j] = cmp(suf[j],suf[j + 1]);
        }
        for(int j = 1;(1 << j) <= C;++j)
            for(int i = 1;i + (1 << j) - 1 <= C;++i)
                st[j][i] = cmp(st[j - 1][i],st[j - 1][i + (1 << (j - 1))]);
        for(int i = 1;i <= C;++i){
            for(int j = bg[i],tp = 0;j <= ed[i];++j){
                if(j != bg[i]) val[j] = val[j - 1];
                while(tp && a[j] <= a[stk[tp] + bg[i] - 1]) val[j] ^= 1u << stk[tp--];
                val[j] ^= 1u << (stk[++tp] = j - bg[i] + 1); 
            }
        }
    }

    int qry(int l,int r){
        if(bl[l] == bl[r]) return l + __builtin_ctz(val[r] >> (l - bg[bl[l]] + 1));
        if(bl[l] + 1 == bl[r]) return cmp(suf[l],pre[r]);
        int i = __lg(bl[r] - bl[l] - 1);
        return cmp(cmp(suf[l],pre[r]),cmp(st[i][bl[l] + 1],st[i][bl[r] - (1 << i)]));
    }
}

总体来看，码量好像小于我在网上搜到的四毛子代码，也用不着笛卡尔树，这个算法还是可以的。