皇家守卫

import java.util.Scanner;
import java.util.Stack;

public class Main {
    static int N = 100010, M = (int) (Math.log10(N) / Math.log10(2)) + 3;
    static int[][] f = new int[N][M];
    static int[] high = new int[N], cnt = new int[N];
    static int n, q;

    public static void main(String[] args) {
        /*
            high[i]表示每一个塔的高度
            cnt[i]表示i右边的符合条件的塔的数量
            维护一个单调栈，倒序遍历h数组，先检查单调性，cnt[i]=stack.size()

            x,y的交集为xy之间最大值的cnt值
            最大值采用st表进行简单实现
         */
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        q = sc.nextInt();
        for (int i = 1; i <= n; i++) {
            high[i] = sc.nextInt();
        }
        init();
        Stack<Integer> stack = new Stack<>();
        for (int i = n; i >= 1; i--) {
            while (!stack.isEmpty() && high[stack.peek()] <= high[i]) {
                stack.pop();
            }
            cnt[i] = stack.size();
            stack.push(i);
        }
        for (int i = 0; i < q; i++) {
            int x = sc.nextInt(), y = sc.nextInt();
            System.out.println(cnt[query(x, y)]);
        }
    }

    static int query(int l, int r) {
        int k = (int) (Math.log10(r - l + 1) / Math.log10(2));
        int left = f[l][k], right = f[r - (1 << k) + 1][k];
        if (high[left] > high[right]) return left;
        else return right;
    }

    static void init() {
        //存储最大值的索引
        for (int j = 0; j < M; j++) {
            for (int i = 1; i + (1 << j) - 1 <= n; i++) {
                if (j == 0) f[i][j] = i;
                else {
                    int left = f[i][j - 1], right = f[i + (1 << (j - 1))][j - 1];
                    if (high[left] > high[right]) f[i][j] = left;
                    else f[i][j] = right;
                }
            }
        }
    }
}