$回滚莫队$
$时间复杂度:O(M\sqrt{N})$
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 200010, M = 10010;
struct Query {
int id, l, r;
} q[M];
int len;
int n, m;
LL a[N], res[N];
vector<LL> nums;
int get(int x)
{
return x / len;
}
void add(int x, LL &ans)
{
ans = max(ans, nums[x]);
}
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i ++) scanf("%lld", &a[i]);
len = sqrt(n);
for(int i = 1; i <= n; i ++) nums.push_back(a[i]);
sort(nums.begin(), nums.end());
nums.erase(unique(nums.begin(), nums.end()), nums.end());
for(int i = 1; i <= n; i ++)
a[i] = lower_bound(nums.begin(), nums.end(), a[i]) - nums.begin();
scanf("%d", &m);
for(int i = 0; i < m; i ++)
{
int l, r;
scanf("%d%d", &l, &r);
q[i] = {i, l, r};
}
sort(q, q + m, [&](const Query &x, const Query &y) {
int i = get(x.l), j = get(y.l);
if(i == j) return x.r < y.r;
return i < j;
});
for(int x = 0; x < m; )
{
int y = x;
while(y < m && get(q[x].l) == get(q[y].l)) y ++;
int mr = get(q[x].l) * len + len - 1;
while(x < y && get(q[x].l) == get(q[x].r))
{
LL ans = -2e18;
int id = q[x].id, l = q[x].l, r = q[x].r;
for(int i = l; i <= r; i ++) add(a[i], ans);
res[id] = ans;
x ++;
}
LL ans = -2e18;
int i = mr, j = mr + 1;
while(x < y)
{
int id = q[x].id, l = q[x].l, r = q[x].r;
while(i < r) add(a[++ i], ans);
LL backup = ans;
while(j > l) add(a[-- j], ans);
res[id] = ans;
j = mr + 1;
ans = backup;
x ++;
}
}
for(int i = 0; i < m; i ++) printf("%lld\n", res[i]);
return 0;
}