基于状压的 O(n)-O(1) rmq

一个很简单的“禁术”。

RMQ

设序列长度为 $n$。

对序列分块，每块长度 $\log_2n$，块数 $n/\log_2n$，记录每块最大值，用 st 表预处理出块件最大值，这一步复杂度为 $O(n)$。

预处理出每一块前后缀最大值，这样当询问的两个端点不在同一个块内，就可以 $O(1)$ 回答了。

现在要处理询问端点在一个块内的情况。

对于一个块的所有前缀，维护一个递减的单调栈，并记录哪些元素在单调栈里（用一个整数状压存储）。

这样 $[l,r]$ 的最大值位置就是前缀 $r$ 的单调栈中第一个在原数组中下标大于等于 $l$ 的位置，即第 $l$ 位后第一个 $1$。

Code

使用了常数略大的写法，为了卡常可以在预处理的时候把多个循环合并为一个。

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

bool MEM1;

namespace solve
{
    const int maxn = 2e7 + 3;

    int len;

    int f[25][maxn / 24 + 7];
    int pre[maxn], suf[maxn], id[maxn], idn, s[maxn];
    int pos[maxn], lg[maxn];

    int n, a[maxn], q;

    void init()
    {
        len = __lg(n);
        lg[0] = -1;
        id[0] = -1;
        static int stk[30], top;
        for (int i = 1; i <= n; i++)
        {
            lg[i] = lg[i >> 1] + 1;
            id[i] = (i - 1) / len + 1;
            if (id[i] == id[i - 1])
                pos[i] = pos[i - 1] + 1;
            else
                pos[i] = 0;
            f[0][id[i]] = max(f[0][id[i]], a[i]);
        }
        idn = id[n];
        for (int i = 1; i <= lg[idn]; i++)
            for (int j = 1; j + (1 << i) - 1 <= idn; j++)
                f[i][j] = max(f[i - 1][j], f[i - 1][j + (1 << (i - 1))]);
        for (int i = 1; i <= n; i++)
            if (id[i] != id[i - 1])
                pre[i] = a[i];
            else
                pre[i] = max(pre[i - 1], a[i]);
        for (int i = n; i >= 1; i--)
            if (id[i] != id[i + 1])
                suf[i] = a[i];
            else
                suf[i] = max(suf[i + 1], a[i]);
        for (int i = 1; i <= n; i++)
        {
            if (id[i] != id[i - 1])
                top = 0;
            else
                s[i] = s[i - 1];
            while (top && a[stk[top]] <= a[i])
                s[i] ^= 1 << pos[stk[top--]];
            s[i] |= 1 << pos[stk[++top] = i];
        }
    }

    inline int query(int l, int r)
    {
        int idl = id[l], idr = id[r];
        if (idl != idr)
        {
            int ans = max(suf[l], pre[r]);
            if (idr - idl > 1)
            {
                int d = lg[idr - idl - 1];
                ans = max(ans, max(f[d][idl + 1], f[d][idr - (1 << d)]));
            }
            return ans;
        }
        else
            return a[l + __builtin_ctz(s[r] >> pos[l])];
    }

    void main()
    {
        cin >> n >> q;
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        init();
        while (q--)
        {
            int l, r;
            cin >> l >> r;
            cout << query(l, r) << '\n';
        }
    }
}

bool MEM2;

int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    solve::main();
}

RMQ¶

Code¶

RMQ

Code