题目

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10, M = 20;
int st[N][M];
int n, m;
int main()
{ios::sync_with_stdio(0);cin.tie(0);cin >> n;for(int i = 1; i <= n; i++)cin >> st[i][0];for(int i = 1; (1 << i) <= n; i++){for(int j = 1; j + (1 << i) - 1 <= n; j++){st[j][i] = max(st[j][i-1], st[j + (1 << i-1)][i-1]); //先跳i-1，再跳i-1}}cin >> m;while (m -- ){int l, r;cin >> l >> r;int k = log2(r-l+1);cout << max(st[l][k], st[r-(1<<k)+1][k]) << endl; //k大小小于等于len，2k一定大于len，可重不漏地考虑最大值}
}