題目描述
給定一個長度為 N 的數列，和 M 次詢問，求出每一次詢問的區間內數字的最大值。
輸入描述
第一行包含兩個整數 N,M，分別表示數列的長度和詢問的個數。
第二行包含 N 個整數（記為𝑎𝑖），依次表示數列的第 i 項。接下來 M 行，每行包含兩個整數?
𝑙𝑖,𝑟𝑖，表示查詢的區間為
[𝑙𝑖,𝑟𝑖]。
輸出描述
輸出包含 M 行，每行一個整數，依次表示每一次詢問的結果。
提示
【數據范圍】
1≤𝑁,𝑀≤105,0≤𝑎𝑖≤109
輸入樣例
8 8
9 3 1 7 5 6 0 8
1 6
1 5
2 7
2 6
1 8
4 8
3 7
1 8
輸出樣例
9
9
7
7
9
8
7
9

?
#include <iostream>
using namespace std;int f[100005][17];
int logn[100005];int main() {int n, m;cin >> n >> m;for (int i = 1; i <= n; i++)cin >> f[i][0];for (int j = 1; 1<<j <= n; j++)for (int i = 1; i+(1<<j)-1 <= n; i++)f[i][j] = max(f[i][j-1], f[i+(1<<(j-1))][j-1]);logn[1] = 0;for (int i = 2; i <= n; i++)logn[i] = logn[i/2] + 1;int l, r;for (int i = 0; i < m; i++) {scanf("%d %d", &l, &r);int x = logn[r-l+1];int mmax = max(f[l][x], f[r-(1<<x)+1][x]);printf("%d\n", mmax);}return 0;
}?