CF1707E Replace

发布于 2022-07-20  3.15k 次阅读


Problem Link

Statement

定义函数 $f$ 如下:

$$
f\big((l,~r)\big) = (\min_{i = l}^r a_i,~\max_{i = l}^r a_i)
$$

给出长度为 $n$ 的值域为 $1 \sim n$ 序列 $a$,$q$ 个询问,每次询问给出 $l_i,~r_i$,问 $(l_i,~r_i)$ 通过多少次 $f$ 操作后达到 $(1,~n)$,或判断无法达到。

$n,~q \le 10^5$

Solution

考虑对于一个点 $p$,当其同时存在于 $[l_1,~r_1]$ 和 $[l_2,~r_2]$ 内时,由于 $\min_{i = l_1}^{r_1} a_i \le a_p \le \max_{i = l_1}^{r_1} a_i$,所以 $a_p \in f\big((l_1,~r_1)\big)$,同理 $a_p \in f\big((l_2,~r_2)\big)$。也就是说,当两个区间有交时,他们各进行一次 $f$ 操作后分别得到的两个新区间也同样有交。

对于 $[l_1,~r_1],~[l_2,~r_2]~(l_1 \le l_2 \le r_1 \le r_2)$,显然有 $f\big((l_1,~r_2)\big) = f\big((l_1,~r_1)\big) \bigcup f\big((l_2,~r_2)\big)$。而我们通过上面的结论可知等号右侧的两个区间有交,可以通过对左端点取较小值,右端点取较大值的方法得到他们的并。

这启发我们得到:$f\big((l,~r)\big) = \bigcup_{i = l}^{r - 1} f\big((i,~i + 1)\big)$。若预处理得到 $f\big((i,~i + 1)\big) = (x_i,~y_i)$,则 $f\big((l,~r)\big) = (\min_{i = l}^{r - 1} x_i, \max_{i = l}^{r - 1} y_i)$,可通过两个 ST 表做到 $O(1)$ 得出答案。

考虑当我们需要进行多次 $f$ 操作时需要如何计算,由于 $f^{a + b}\big((l,~r)\big) = f^a\Big(f^b\big((l,~r)\big)\Big)$,不难想到使用倍增的思想,对于每个 $k$ 我们预处理 $f^{2^k}\big((i,~i + 1)\big)$,再使用与上面相同的 ST 表维护方法即可 $O(1)$ 算出 $f^{2^k}\big((l,~r)\big)$。

询问 $(l,~r)$ 最少需操作多少次时,我们只需要从大往小枚举 $k$ 找到最大的 $x$ 满足 $f^x\big((l,~r)\big) \neq (1,~n)$,除去无解情况后答案即为 $x + 1$。

总时间复杂度 $O((n + q) \log n)$。

Code

偷了个懒使用线段树实现。复杂度 $O((n + q) \log^2 n)$,也可通过本题。

View on GitHub

/**
 * @file 1707E.cpp
 * @author Macesuted (i@macesuted.moe)
 * @date 2022-07-17
 *
 * @copyright Copyright (c) 2022
 *
 */

#include <bits/stdc++.h>
using namespace std;

#ifndef LOCAL
#define endl '\n'
#endif

bool mem1;

#define maxn 100005
#define maxlgn 18

typedef pair<int, int> pii;

pii merge(const pii& a, const pii& b) { return {min(a.first, b.first), max(a.second, b.second)}; }

class SegmentTree {
   private:
    pii tree[maxn << 2];
    int n;

    void pushUp(int p) { return tree[p] = merge(tree[p << 1], tree[p << 1 | 1]), void(); }
    void insert(int p, int l, int r, int qp, pii v) {
        if (l == r) return tree[p] = v, void();
        int mid = (l + r) >> 1;
        qp <= mid ? insert(p << 1, l, mid, qp, v) : insert(p << 1 | 1, mid + 1, r, qp, v);
        return pushUp(p);
    }
    pii query(int p, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) return tree[p];
        int mid = (l + r) >> 1;
        if (qr <= mid) return query(p << 1, l, mid, ql, qr);
        if (ql > mid) return query(p << 1 | 1, mid + 1, r, ql, qr);
        return merge(query(p << 1, l, mid, ql, qr), query(p << 1 | 1, mid + 1, r, ql, qr));
    }

   public:
    void resize(int _n) { return n = _n, void(); }
    void insert(int p, pii v) { return insert(1, 1, n, p, v); }
    pii query(pii a) { return a.first >= a.second ? pii{INT_MAX, INT_MIN} : query(1, 1, n, a.first, a.second - 1); }
};

int a[maxn];
SegmentTree ST[maxlgn];

void solve(void) {
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 0; i < maxlgn; i++) ST[i].resize(n);
    for (int i = 1; i < n; i++) ST[0].insert(i, {min(a[i], a[i + 1]), max(a[i], a[i + 1])});
    for (int i = 1; i < maxlgn; i++)
        for (int j = 1; j < n; j++) ST[i].insert(j, ST[i - 1].query(ST[i - 1].query({j, j + 1})));
    while (q--) {
        int l, r;
        cin >> l >> r;
        if (l == 1 && r == n)
            cout << 0 << endl;
        else if (l == r)
            cout << -1 << endl;
        else {
            int ans = 0;
            for (int i = maxlgn - 1; ~i; i--) {
                pii ret = ST[i].query({l, r});
                if (ret != pii{1, n}) ans |= 1 << i, tie(l, r) = ret;
            }
            ans++;
            cout << (ans == (1 << maxlgn) ? -1 : ans) << endl;
        }
    }
    return;
}

bool mem2;

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
#ifdef LOCAL
    cerr << "Memory Cost: " << abs(&mem1 - &mem2) / 1024. / 1024. << "MB" << endl;
#endif

    int _ = 1;
    while (_--) solve();

#ifdef LOCAL
    cerr << "Time Cost: " << clock() * 1000. / CLOCKS_PER_SEC << "MS" << endl;
#endif
    return 0;
}

我缓慢吐出一串啊吧啊吧并不再想说话