F Souvenirs
将询问离线,对原数组离散化,然后用权值线段树维护区间对应权值最大值,\(a_i\) 的权值为 \(i\),再用树状数组维护区间两数绝对值差的最小值。
复杂度为 \(\mathcal{O}(n\log^{2}n+m)\)。
[提交:193500144]
C++ Code
#include <bits/stdc++.h>
using i64 = long long;
template<class Info,
class Merge = std::plus<Info>>
struct SegmentTree {
const int n;
const Merge merge;
std::vector<Info> info;
SegmentTree(int n) : n(n), merge(Merge()), info(4 << std::__lg(n)) {}
SegmentTree(std::vector<Info> init) : SegmentTree(init.size()) {
std::function<void(int, int, int)> build = [&](int p, int l, int r) {
if (r - l == 1) {
info[p] = init[l];
return;
}
int m = (l + r) / 2;
build(2 * p, l, m);
build(2 * p + 1, m, r);
pull(p);
};
build(1, 0, n);
}
void pull(int p) {
info[p] = merge(info[2 * p], info[2 * p + 1]);
}
void modify(int p, int l, int r, int x, const Info &v) {
if (r - l == 1) {
info[p] = v;
return;
}
int m = (l + r) / 2;
if (x < m) {
modify(2 * p, l, m, x, v);
} else {
modify(2 * p + 1, m, r, x, v);
}
pull(p);
}
void modify(int p, const Info &v) {
modify(1, 0, n, p, v);
}
Info rangeQuery(int p, int l, int r, int x, int y) {
if (l >= y || r <= x) {
return Info();
}
if (l >= x && r <= y) {
return info[p];
}
int m = (l + r) / 2;
return merge(rangeQuery(2 * p, l, m, x, y), rangeQuery(2 * p + 1, m, r, x, y));
}
Info rangeQuery(int l, int r) {
return rangeQuery(1, 0, n, l, r);
}
};
template <typename T>
struct Fenwick {
int n;
std::vector<T> a;
Fenwick(int n = 0) {
init(n);
}
void init(int n) {
this->n = n;
a.assign(n, T());
}
void add(int x, T v) {
for (int i = x + 1; i <= n; i += i & -i) {
a[i - 1] += v;
}
}
T sum(int x) {
auto ans = T();
for (int i = x; i > 0; i -= i & -i) {
ans += a[i - 1];
}
return ans;
}
T rangeSum(int l, int r) {
return sum(r) - sum(l);
}
int kth(T k) {
int x = 0;
for (int i = 1 << std::__lg(n); i; i /= 2) {
if (x + i <= n && k >= a[x + i - 1]) {
x += i;
k -= a[x - 1];
}
}
return x;
}
};
struct Max {
int x;
Max(int x = -1) : x(x) {}
};
Max operator+(const Max &a, const Max &b) {
return std::max(a.x, b.x);
}
constexpr int inf = 1E9;
struct Min {
int x;
Min(int x = inf) : x(x) {}
Min &operator+=(Min a) {
x = std::min(a.x, x);
return *this;
}
};
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
std::cin >> n;
std::vector<int> a(n);
for (int i = 0; i < n; i++) {
std::cin >> a[i];
}
auto b = a;
sort(b.begin(), b.end());
b.erase(unique(b.begin(), b.end()), b.end());
const int N = b.size();
for (int i = 0; i < n; i++) {
a[i] = lower_bound(b.begin(), b.end(), a[i]) - b.begin();
}
int m;
std::cin >> m;
std::vector<std::vector<std::pair<int, int>>> qry(n);
for (int i = 0; i < m; i++) {
int l, r;
std::cin >> l >> r;
l--, r--;
qry[r].emplace_back(l, i);
}
SegmentTree<Max> seg(N);
Fenwick<Min> fen(n);
std::vector<int> ans(m);
seg.modify(a[0], 0);
for (int i = 1; i < n; i++) {
int j = seg.rangeQuery(a[i], N).x;
while (j != -1) {
fen.add(n - 1 - j, b[a[j]] - b[a[i]]);
if (a[j] == a[i]) {
break;
}
int num = lower_bound(b.begin(), b.end(), (b[a[j]] + b[a[i]]) / 2 + 1) - b.begin();
j = seg.rangeQuery(a[i], num).x;
}
int k = seg.rangeQuery(0, a[i] + 1).x;
while (k != -1) {
fen.add(n - 1 - k, b[a[i]] - b[a[k]]);
if (a[k] == a[i]){
break;
}
int num = lower_bound(b.begin(), b.end(), (b[a[k]] + b[a[i]] + 1) / 2) - b.begin();
k = seg.rangeQuery(num, a[i] + 1).x;
}
seg.modify(a[i], i);
for (auto &[l, j] : qry[i]) {
ans[j] = fen.sum(n - l).x;
}
}
for (int i = 0; i < m; i++) {
std::cout << ans[i] << '\n';
}
return 0;
}