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)$，也可通过本题。
/**
* @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;
}
Comments | NOTHING