Method of Four Russians

前置：ST表
用来解决区间最值问题(RMQ)

如果将整个数组分块，每一个块的大小是$b$,则可以分出$\frac{n}{b}$
每一个块求一个最小值出来，对这$\frac{n}{b}$个最小值建一个ST表，则时间复杂度$O\left(\frac{n}{b}{\log }_2\frac{n}{b}\right)\subseteq O\left(\frac{n}{b}{\log }_{2}n\right)$

如果块的大小$b\in \Theta \left(\log n\right)$，则时间复杂度为$O\left(n\right)$

但是这个只是块之间的RMQ，查询区间可能是跨越几个块，也可能在块内

这时候如果每一个块建一个ST表,则时间复杂度$O\left(\frac{n}{b}b{\log }_{2}b\right)\subseteq O\left(n{\log }_{2}b\right)$,不太行

考虑在块内使用单调栈,在每一个位置存一个二进制mask，
以求区间最大值为例，则需要维护一个单调递减栈,mask表示还在栈里的元素

假设这个块为$1,4,2,6,7,4,5,3$
$idx=0,a[idx]=1,mask=00000001b$
$idx=1,a[idx]=4,mask=00000010b$
$idx=2,a[idx]=2,mask=00000110b$
$idx=3,a[idx]=6,mask=00001000b$
$idx=4,a[idx]=7,mask=00010000b$
$idx=5,a[idx]=4,mask=00110000b$
$idx=6,a[idx]=5,mask=01010000b$
$idx=7,a[idx]=3,mask=11010000b$

查询$[0,r]$的最大值，只需要找到$mask[r]$最低位的$1$的索引
查询$[l,r]$的最大值，只需要找到$mask[r]>>pos[l]$的最低位$1$的索引$i$，最大值为$a[l+i]$

这样计算，单调栈时间复杂度$O\left(b\right)$,进而总的时间复杂度为$O\left(\frac{n}{b}b\right)$
总的预处理时间复杂度为$O(n)$

P3865

#include<cstdio>
#include<cmath>
#include<algorithm>

const int N = 1e5 + 5;
const int M = 21;

int n;
int a[N];//原数组
int block_size;//块大小
int st[N][M];//块之间的st表
int Pow[M] = {1};//2的幂
int logn[N] = {-1, 0};//log2 n
int belong[N];//元素属于哪一个块
int pos[N];//块中的索引
int pre[N];//前缀最值
int sub[N];//后缀最值
int mask[N];//二进制mask

int s[N], top;//栈

void build_st() {
    int cur = 0;
    int id = 1;//块索引
    pos[0] = -1;
    for (int i = 1; i <= n; ++i) {
        st[id][0] = std::max(st[id][0], a[i]);//块内最值
        belong[i] = id;
        if (belong[i - 1] != belong[i]) {
            pos[i] = 0;
        }
        else {
            pos[i] = pos[i - 1] + 1;
        }

        if (++cur == block_size) {
            cur = 0;
            ++id;
        }
    }

    if (n % block_size == 0) --id;
    //预处理2的幂
    for (int i = 1; i < M; ++i)Pow[i] = Pow[i - 1] << 1;
    //预处理log2
    for (int i = 2; i <= id; ++i)logn[i] = logn[i >> 1] + 1;
    //块间st表预处理
    for (int j = 1; j <= logn[id]; ++j) {
        for (int i = 1; i + Pow[j] - 1 <= id; ++i) {
            st[i][j] = std::max(st[i][j - 1], st[i + Pow[j - 1]][j - 1]);
        }
    }

}

void build_sub_pre() {
    for (int i = 1; i <= n; ++i) {
        if (belong[i] != belong[i - 1]) {
            pre[i] = a[i];
        }
        else {
            pre[i] = std::max(pre[i - 1], a[i]);
        }
    }

    for (int i = n; i >= 1; --i) {
        if (belong[i] != belong[i + 1]) {
            sub[i] = a[i];
        }
        else {
            sub[i] = std::max(sub[i + 1], a[i]);
        }
    }
}

void build_block() {
    for (int i = 1; i <= n; ++i) {
        if (belong[i] != belong[i - 1]) {
            top = 0;
        }
        else {
            mask[i] = mask[i - 1];
        }

        while (top > 0 && a[s[top]] <= a[i]) {
            //去掉这个位置上的1
            mask[i] &= ~(1 << pos[s[top--]]);
        }

        s[++top] = i;
        mask[i] |= (1 << pos[i]);
    }
}

void init() {
    block_size = log2(n) * 1.5;
    build_st();
    build_sub_pre();
    build_block();
}

int query(int l, int r) {
    int bl = belong[l], br = belong[r];
    if (bl != br) {//跨块
        int ans1 = 0;
        if (br - bl > 1) {//块间
            //bl + 1 -> br - 1
            int p = logn[br - bl - 1];
            ans1 = std::max(st[bl + 1][p], st[br - Pow[p]][p]);
        }
        //左边和右边多出来的部分
        int ans2 = std::max(sub[l], pre[r]);
        return std::max(ans1, ans2);
    }
    //块内
    return a[l + __builtin_ctz(mask[r] >> pos[l])];
}

int main() {
    int m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }
    init();
    while(m--){
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", query(l, r));
    }
    return 0;
}

参考：
https://oi-wiki.org/topic/rmq/#four-russian
https://codeforces.com/blog/entry/78931