#include <bits/stdc++.h>
using namespace std;
const int N = (int) 5e5 + 7;
const int INF = (int) 2e9;
int n, a[N], nextBigger[N], q;
struct rmq {
const int K = 20;
vector<vector<int>> tab;
vector<int> lg2;
int n;
void init(int nn) {
n = nn;
lg2.resize(n + 1);
for (int i = 2; i <= n; i++) {
lg2[i] = 1 + lg2[i / 2];
}
tab.resize(K);
for (int i = 0; i < K; i++) {
tab[i].resize(n + 1);
}
}
void build(int a[]) {
for (int i = 1; i <= n; i++) {
tab[0][i] = a[i];
}
for (int k = 1; k < K; k++) {
for (int i = 1; i + (1 << k) - 1 <= n; i++) {
tab[k][i] = max(tab[k - 1][i], tab[k - 1][i + (1 << (k - 1))]);
}
}
}
int query(int x, int y) {
if (x > y) {
return -INF;
}
assert(1 <= x && x <= y && y <= n);
int p = lg2[y - x + 1];
return max(tab[p][x], tab[p][y - (1 << p) + 1]);
}
};
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
///freopen("input", "r", stdin);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
rmq rmq;
rmq.init(n);
rmq.build(a);
if (n <= 5000) {
vector<vector<int>> mx(n + 1, vector<int>(n + 1));
for (int l = 1; l <= n; l++) {
for (int r = l + 1; r <= n; r++) {
3, 6 => 3 4
5 10 =>
1 10 => 2 3 4 5
mx[l][r] = a[l] + a[r] + rmq.query(l + 1, (l + r) / 2);
}
}
for (int l = n; l >= 1; l--) {
for (int r = l + 2; r <= n; r++) {
mx[l][r] = max(mx[l][r], mx[l][r - 1]);
mx[l][r] = max(mx[l][r], mx[l + 1][r]);
}
}
cin >> q;
while (q--) {
int l, r;
cin >> l >> r;
cout << mx[l][r] << "\n";
}
return 0;
}
{
vector<int> st;
for (int i = n; i >= 1; i--) {
while (!st.empty() && a[i] >= a[st.back()]) {
st.pop_back();
}
if (st.empty()) {
nextBigger[i] = n + 1;
} else {
nextBigger[i] = st.back();
}
st.push_back(i);
}
}
cin >> q;
for (int iq = 1; iq <= q; iq++) {
int l, r, best = 0;
cin >> l >> r;
for (int i = l; i <= r; i++) {
for (int j = i + 1; j <= min(n, nextBigger[i]); j = nextBigger[j]) {
best = max(best, a[i] + a[j] + rmq.query(2 * j - i, r));
}
}
cout << best << "\n";
}
return 0;
}
Compilation message
jumps.cpp: In function 'int main()':
jumps.cpp:63:15: error: expected primary-expression before '>' token
63 | 3, 6 => 3 4
| ^
