算法分析

RMQ算法只能解决询问操作

状态表示：$f[i,j]$表示从$i$开始长度是$2^j$的区间中的最大值

• 1、先预处理出所有f[i,j]的状态，因为图片中状态转移的时候i是跳动的，j是依赖于j - 1，因此需要先枚举j，再枚举i，还需要预处理出2^k的值
• 2、查询操作时，需要先算出区间的长度len = b - a + 1，再通过二分算出最大的2^k <= len的k，因此[a,a + 2^k - 1]和[b - 2^k + 1,k]一定能全部覆盖[a,b]的区间，因此只需要求f[a,k]和f[b - 2^k + 1,k]的最大值即可

时间复杂度 $nlogn$

参考文献

算法提高课

Java 代码

import java.util.Scanner;
public class Main
{
    static int N = 2 * 100000 + 10,M = 18;  //2^17 < N < 2^18
    static int[][] f = new int[N][M];
    static int[] w = new int[N];
    static int n,m;
    static int[] qmi = new int[M];
    static void init()
    {
        qmi[0] = 1;
        for(int i = 1;i < M;i ++)
        {
            qmi[i] = qmi[i - 1] * 2;
        }

        for(int j = 0;j < M;j ++)
            for(int i = 1;i + qmi[j] - 1 <= n;i ++)
                if(j == 0) f[i][j] = w[i];
                else f[i][j] = Math.max(f[i][j - 1], f[i + qmi[j - 1]][j - 1]);
    }
    static int query(int a,int b)
    {
        int len = b - a + 1;
        //2^k <= len，找k
        int l = 0,r = 17;
        while(l < r)
        {
            int mid = l + r + 1 >> 1;
            if(qmi[mid] <= len) l = mid;
            else r = mid - 1;
        }

        return Math.max(f[a][l], f[b - qmi[l] + 1][l]);
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        for(int i = 1;i <= n;i ++) w[i] = scan.nextInt();

        init();

        m = scan.nextInt();
        while(m -- > 0)
        {
            int l = scan.nextInt();
            int r = scan.nextInt();
            System.out.println(query(l,r));
        }
    }
}