CF1793 - Codeforces Round

Codeforces Round #852 (Div. 2)

F. Rebrending

题意

区间长度为$n$的数组$a[i]$，且满足$a[i]\in[1,n]$，有$q$个查询区间$[l_1,r_i]$，对于每个查询区间，求出
$a_{l_i},a_{l_i+1},\cdots, a_{r_i-1},a_{r_i}$ 中相差最小的值，即

$$\min_{j,k\in[l_i,r_i]} |a_j-a_k|$$

思路

该题不好直接构造线段树维护差值最小值，考虑离线做法.

令当前考虑右端点在 $r$ 处的查询 $S_r = \{[l_i,r_i]: r_i = r\}$，设 $dp(i)$ 为 $a_i$ 与 $\{a_{i+1},\cdots, a_r\}$ 的最小差值，即 $dp(i) = \min\{|a_i-a_j|:i+1\leqslant j\leqslant r\}$.

从左到右依次扫描 $r$，考虑如何使用 $a_r$ 更新 $1\leqslant i\leqslant r-1$ 的dp值.

设 $l_1 = \max\{l:a_l\geqslant a_r\}$ 为距离 $r$ 最近且比 $a_r$ 大的值，若 $i \lt l_1 \lt r$ 且 $\displaystyle a_i \geqslant \frac{a_{l_1}+a_r}{2}$，则 $a_i$ 离 $a_{l_1}$ 的距离不低于 $a_i$，所以无需更新. 所以要找

$$l_2 = \max\left\{l:a_r\leqslant a_{l}\leqslant \left\lfloor \frac{a_{l_1}+a_r}{2}\right\rfloor\right\}$$

依此类推：

$$l_{k+1} = \max\left\{l:a_r\leqslant a_{l}\leqslant \left\lfloor \frac{a_{l_k}+a_r}{2}\right\rfloor\right\}$$

直到 $a_{l_k} = a_r$ 或者 $\displaystyle \varnothing = \left\{l : a_r\leqslant a_l\leqslant \left\lfloor\frac{a_{l_k}+a_r}{2}\right\rfloor\right\}$，于是我们只需更新 $l\in\{l_1,\cdots, l_k\}$ 的dp值为 $dp(l) = \min\{dp(l), a_l-a_r\}$.

对于 $a_l \lt a_r$ 与 $a_l > a_r$ 处理类似，只需找

$$l_{k+1} = \max\left\{l:\left\lfloor \frac{a_{l_k}+a_r}{2}\right\rfloor\leqslant a_{l}\leqslant a_r\right\}$$

由于值域为 $[1,n]$ 则更新节点数为 $\mathcal{O}(\log n)$，用线段树查找 $l_k$ 用时 $\mathcal{O}(\log n)$，总计用时 $\mathcal{O}(n\log^2n)$.

对于每个询问 $[l_i,r_i]$，当右端点 $r=r_i$ 时，答案为 $\min\limits_{l_i\leqslant l \lt r_i}dp(l)$，用另一颗线段树记录dp值即可，用时 $\mathcal{O}(q\log n)$.

具体算法步骤：

1. 离线全部询问，以右端点进行排序.
2. 构造两颗线段树：
   1. key: Id, value: dp值，找区间最小值
   2. key: $a_i$，value: Id，找区间最大值.

点击显/隐代码

/*
* File    : F.cpp
* Time    : 2023/02/17 15:56:24
* Author  : wty-yy
* Version : 1.0
* Blog    : https://wty-yy.space/
* Desc    : https://codeforces.com/contest/1793/problem/F
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <math.h>
#include <vector>
#include <map>
#define ll long long
#define ls (p << 1)
#define rs (p << 1 | 1)
using namespace std;

const int N = 3e5 + 10;
const int Q = 1e6 + 10;
const int MAX = 0x7FFFFFFF;
const int MIN = -MAX;

int n, q, dp[N], a[N], ans[Q];

struct SegmentTree {
    int mn[N<<2], mx[N<<2];

    void init(int n) {
        for (int i = 1; i <= 4*n; i++) {
            mx[i] = MIN;
            mn[i] = MAX;
        }
    }

    void pushup(int p) {
        mn[p] = min(mn[ls], mn[rs]);
        mx[p] = max(mx[ls], mx[rs]);
    }

    void change(int p, int l, int r, int x, int val) {
        if (l == x && r == x) {
            mn[p] = min(mn[p], val);
            mx[p] = max(mx[p], val);
            return;
        }
        int mid = (l + r) >> 1;
        if (x <= mid) change(ls, l, mid, x, val);
        else change(rs, mid + 1, r, x, val);
        pushup(p);
    }

    int get(int p, int l, int r, int L, int R, bool is_max) {
        if (r < L || l > R) return is_max ? MIN : MAX;
        if (l >= L && r <= R) return is_max ? mx[p] : mn[p];
        int mid = (l + r) >> 1;
        if (R <= mid) return get(ls, l, mid, L, R, is_max);
        else if (L > mid) return get(rs, mid + 1, r, L, R, is_max);
        else {
            int vl = get(ls, l, mid, L, mid, is_max), vr = get(rs, mid + 1, r, mid + 1, R, is_max);
            return is_max ? max(vl, vr) : min(vl, vr);
        }
    }
}seg_dp, seg_id;

struct Query {
    int id, l, r;
    bool operator < (Query b) { return r < b.r; }
}query[Q];

void update(int r, bool is_big) {  // 用a[r]更新[1,...,r-1]的dp值，最多更新logn个
    int L = is_big ? a[r] : MIN, R = is_big ? MAX : a[r], l;
    while (1) {
        l = seg_id.get(1, 1, n, L, R, 1);
        if (l == MIN || l == MAX) break;
        dp[l] = min(dp[l], abs(a[l] - a[r]));
        seg_dp.change(1, 1, n, l, dp[l]);
        if (a[l] == a[r]) break;

        if (is_big) R = (a[l] + a[r]) >> 1;
        else L = (a[l] + a[r] + 1) >> 1;
    }
}

int main() {
    memset(dp, 0x3f, sizeof(dp));
    scanf("%d %d", &n, &q);
    seg_dp.init(n), seg_id.init(n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 0; i < q; i++) {
        scanf("%d %d", &query[i].l, &query[i].r);
        query[i].id = i;
    }
    sort(query, query + q);
    int i = 0, r = 1;
    while (i < q) {
        update(r, 0); update(r, 1);
        while (i < q && query[i].r == r) {
            ans[query[i].id] = seg_dp.get(1, 1, n, query[i].l, query[i].r, 0);
            i++;
        }
        seg_id.change(1, 1, n, a[r], r);
        r++;
    }
    for (int i = 0; i < q; i++) printf("%d\n", ans[i]);
    return 0;
}