天才的记忆
思路
image.png
代码
#include <iostream>
#include <cmath>
using namespace std;
const int N = 200010, M = 18;
int q[N];
int n, m, a, b;
int f[N][M];
void ok()
{
for (int i = 1; i <= n; i ++ ) f[i][0] = q[i - 1];
int len = log(n) / log(2);
for (int j = 1; j <= len; 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]);
}
int go(int a, int b)
{
int len = log(b - a + 1) / log(2);
return max(f[a][len], f[b - (1 << len) + 1][len]);
}
int main()
{
cin >> n;
for (int i = 0; i < n; i ++ ) cin >> q[i];
ok();
cin >> m;
while (m --)
{
cin >> a >> b;
cout << go(a, b) << endl;
}
return 0;
}
