F. Rebrending
题目抽象为现有长度为 \(n\) 的数组 \(a_1,a_2,\cdots,a_n\)，\(m\) 次询问，每次询问 \(\min\limits_{l\le i,j\le r,i\neq j} |a_i-a_j|\) \((1\le l< r\le n)\)。
此题和 CF765F 几乎一样，但是还是和原题有一些不一样的地方，询问次数更多，并且 \(a_i\le n\)。原题有一种做法是按 \(r\) 的大小排序将询问离线，用权值线段树维护区间对应权值最大值，\(a_i\) 的权值为 \(i\)，再用树状数组或线段树维护区间两数绝对值差的最小值，原题 \(a_i\le 10^9\), 那么需要离散化或者动态开点，复杂度为 \(\mathcal{O}(n\log n\log 10^9+m\log n)\)。
那么我们还是考虑离线，因为 \(r\le n\)，那么就不需要排序了，从左往右遍历所有元素，遍历到 \(a_i\) 时回答 \(r=i\) 的询问，那么我们只需要考虑 \(i-1\rightarrow i\) 对答案的影响。
\(a_j>a_i\) (\(l\le j\le r\)) 对答案的贡献为 \(a_j-a_i\)。
\(a_k<a_i\) (\(l\le k\le r\)) 对答案的贡献为 \(a_i-a_k\)。
先找到最大的 \(j\) 满足 \(a_j>a_i\)，更新区间最小值，此时还可能存在 \(y\) 满足 \(a_y-a_i<a_j-a_i\)，接着查询 \([a_i,\lfloor\frac{a_i+a_j}{2}\rfloor]\) 中最大的 \(y\) 满足 \(a_y>a_i\)，一直重复查询直到不存在比 \(a_i\) 大的数，最多查询 \(\log i\) 次。
区间中比 \(a_i\) 小的数对答案的贡献和上述基本一样。
这里用树状数组维护区间两数绝对值差的最小值。
复杂度为 \(\mathcal{O}(n\log^{2}n)\)。
提交记录：
193417542
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, m;
std::cin >> n >> m;
std::vector<int> a(n);
for (int i = 0; i < n; i++) {
std::cin >> a[i];
a[i]--;
}
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, a[j] - a[i]);
j = seg.rangeQuery(a[i], (a[i] + a[j]) / 2 + 1).x;
}
int k = seg.rangeQuery(0, a[i] + 1).x;
while (k != -1) {
fen.add(n - 1 - k, a[i] - a[k]);
k = seg.rangeQuery((a[i] + a[k] + 1) / 2, 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;
}