- #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;
- }
区间最值
ST 表
来源: http://www.bubuko.com/infodetail-3164754.html