ST表

#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;
int read()
{
    int x = 0 , fx = 1;
    char ch = getchar();
    while(ch > ‘9‘ || ch < ‘0‘)
    {
        if(ch == ‘-‘)
            fx = -1;
        ch = getchar();
    }
    while(ch >= ‘0‘ && ch <= ‘9‘)
    {
        x = (x << 3) + (x << 1) + (ch & 15);
        ch = getchar();
    }
    return x * fx;
}
int a[100005][21];
int query(int l , int r)
{
    int k = log2(r - l + 1);
    return max(a[l][k] , a[r - (1 << k) + 1][k]);
}
int main()
{
    int n , m , l , r;
    n = read() , m = read();
    for(int i = 1; i <= n; i++)
        a[i][0] = read();
    for(int j = 1; j <= 20; j++)
        for(int i = 1; i + (1 << j) - 1 <= n; i++)
            a[i][j] = max(a[i][j - 1] , a[i + (1 << (j - 1))][j - 1]);
    for(int i = 1; i <= m; i++)
    {
        l = read() , r = read();
        printf("%d\n" , query(l , r));
    }
    return 0;
}