CF765F 维护区间任意数对差的绝对值的最小值

qwq

一句话题意:维护区间任意数对差的绝对值的最小值。

显然可以莫队 + 平衡树水过。此题完结(bushi

考虑离线做,容易想到把区间按右端点排序,维护左端点 $i \in [1, r)$ 的答案 $ans_{i, r}$。移动右指针,每次移动暴力修改答案。

考虑优化暴力,用线段树维护答案。每个节点用 vector 存区间 [L, R] 的所有 w 值,每次修改 lower_bound 查出来然后修改。然后我们的复杂度就更劣了。

可以给线段树剪枝。$ans_{i, r}$ 实际上是 $\min \limits_{i}^{r - 1}$,所以 ans 实际上是单调不升的。每次修改可以维护一个全局的修改后 ans 最小值 mini,当目前节点修改后答案大于 mini,可以直接 return。就过了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <bits/stdc++.h>

typedef long long LL;
const int N = 1000000 + 233;
const LL INF = 1ll << 62;
int n, q;
LL w[N], res[N << 2], mini, ans[N];
std::vector<LL> t[N << 2];
struct Interval {
int l, r, id;
friend bool operator <(Interval x, Interval y) {
return x.r < y.r;
}
} ask[N];

void build(int p, int l, int r) {
for (int i = l; i <= r; ++i) t[p].push_back(w[i]);
std::sort(t[p].begin(), t[p].end());
res[p] = INF;
if (l == r) return;
int mid = (l + r) >> 1;
build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r);
}

void modify(int p, int l, int r, int x, LL d) {
if (r <= x) {
std::vector<LL>::iterator it = std::lower_bound(t[p].begin(), t[p].end(), d);
if (it != t[p].end()) res[p] = std::min(res[p], *it - d);
if (it != t[p].begin()) res[p] = std::min(res[p], d - *(it - 1));
if (mini <= res[p]) return;
if (l == r) return (void)(mini = std::min(mini, res[p]));
}
int mid = (l + r) >> 1;
if (x > mid) modify(p << 1 | 1, mid + 1, r, x, d);
modify(p << 1, l, mid, x, d);
res[p] = std::min(res[p], std::min(res[p << 1], res[p << 1 | 1]));
mini = std::min(mini, res[p]);
}

LL query(int p, int l, int r, int pl, int pr) {
if (l >= pl && r <= pr) return res[p];
int mid = (l + r) >> 1;
LL ret = INF;
if (pl <= mid) ret = std::min(ret, query(p << 1, l, mid, pl, pr));
if (pr > mid) ret = std::min(ret, query(p << 1 | 1, mid + 1, r, pl, pr));
return ret;
}

signed main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%lld", w + i);
scanf("%d", &q);
for (int i = 1; i <= q; ++i) {
scanf("%d%d", &ask[i].l, &ask[i].r);
ask[i].id = i;
}
std::sort(ask + 1, ask + 1 + q);
build(1, 1, n);
for (int i = 2, ptr = 1; i <= n; ++i) {
mini = INF;
modify(1, 1, n, i - 1, w[i]);
while (ptr <= q && ask[ptr].r <= i) {
ans[ask[ptr].id] = query(1, 1, n, ask[ptr].l, i);
++ptr;
}
}
for (int i = 1; i <= q; ++i) printf("%lld\n", ans[i]);
return 0;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×