CF1707E 题解

· · 题解

题目链接

题意描述：给定长度为 n 的序列 a（1\le a_i\le n）。

定义 \min(S)=\min\limits_{i\in S}a_i。

定义 \max(S)=\max\limits_{i\in S}a_i。

定义 [l,r]=\{x\in\mathbb{N}|l\le x\le r\}。

定义

f^0([l,r])=[l,r] f^1([l,r])=[\min([l,r]),\max([l,r])] f^k([l,r])=f^1(f^{k-1}([l,r]))\ \ \ \ (k>1) 神仙思维题。考察的算法不难，但考的是灵活应用 ~~（和极强的找性质能力~~。 首先，静态区间求最值，$\text{ST}$ 表即可解决。 然后，如果你像 $\text{Alice}$ 和 $\text{Bob}$ 一样聪明，你就可以看出如果两个区间 $[l_1,r_1]\cap[l_2,r_2]\neq\varnothing$，那么 $f([l_1,r_1])\cap f([l_2,r_2])\neq\varnothing$，且 $f([l_1,r_1])\cup f([l_2,r_2])=f([l_1,r_1]\cup[l_2,r_2])$。 证明如下： 如果两个区间 $[l_1,r_1]\cap[l_2,r_2]\neq\varnothing$， 那么 $\max([l_1,r_1])\ge\max([l_1,r_1]\cap[l_2,r_2])\ge\min([l_1,r_1]\cap[l_2,r_2])\ge\min([l_2,r_2]) \max([l_2,r_2])\ge\max([l_2,r_2]\cap[l_1,r_1])\ge\min([l_2,r_2]\cap[l_1,r_1])\ge\min([l_1,r_1])

即 f([l_1,r_1])\cap f([l_2,r_2])\neq\varnothing。

而

\max([l_1,r_1]\cup[l_2,r_2])=\max(\max([l_1,r_1]),\max([l_2,r_2])) \min([l_1,r_1]\cup[l_2,r_2])=\min(\min([l_1,r_1]),\min([l_2,r_2]))

即 f([l_1,r_1])\cup f([l_2,r_2])=f([l_1,r_1]\cup[l_2,r_2])。

所以如果 [l_1,r_1]\cap[l_2,r_2]\neq\varnothing，那么 f^k([l_1,r_1])\cap f^k([l_2,r_2])\neq\varnothing，且 f^k([l_1,r_1])\cup f^k([l_2,r_2])=f^k([l_1,r_1]\cup[l_2,r_2])。

发现它像区间最值一样可以合并。于是设 g_{i,j,k} 为 f^{2^j}([i,i+2^k-1])，然后可以倍增转移。时间 O(n\log^2n)。

还有最后一件事，答案的上界是 2n，如果拓展了超过 2n 次就无解。

#include <bits/stdc++.h>
using namespace std;
namespace QYB {
    int n, q, a[100005], log2[100005], minn[18][100005], maxn[18][100005];
    pair<int, int> g[18][18][100005];
    pair<int, int> extend(pair<int, int> s, int k) {
        // 利用 g 数组将 s 拓展 2 ^ k 次
        int l = s.first, r = s.second, t = log2[r - l + 1];
        pair<int, int> s1 = g[k][t][l], s2 = g[k][t][r - (1 << t) + 1];
        return make_pair(min(s1.first, s2.first), max(s1.second, s2.second));
    } int main() {
        scanf("%d%d", &n, &q); log2[0] = -1;
        for (int i = 1; i <= n; i++) {
            scanf("%d", a + i); log2[i] = log2[i / 2] + 1;
            minn[0][i] = maxn[0][i] = a[i];
        } for (int i = 1; i <= 17; i++) {
            for (int j = 1; j + (1 << i) - 1 <= n; j++) {
                maxn[i][j] = max(maxn[i - 1][j], maxn[i - 1][j + (1 << i - 1)]);
                minn[i][j] = min(minn[i - 1][j], minn[i - 1][j + (1 << i - 1)]);
            }
        } for (int i = 1; i <= 17; i++) {
            for (int j = 1; j + (1 << i) - 1 <= n; j++) {
                g[0][i][j] = make_pair(minn[i][j], maxn[i][j]);
            }
        } for (int i = 1; i <= 17; i++) {
            for (int j = 1; j <= 17; j++) {
                for (int k = 1; k + (1 << j) - 1 <= n; k++) {
                    // 由于这个时候 g[i - 1][][] 已经计算完毕了，所以这时调用 extend 是可以的
                    g[i][j][k] = extend(extend(make_pair(k, k + (1 << j) - 1), i - 1), i - 1);
                }
            }
        } while (q--) {
            int l, r, ans = 0; scanf("%d%d", &l, &r);
            if (l == 1 && r == n) { printf("0\n"); continue; }
            // 特判一手，因为下面至少会拓展 1 次
            for (int i = 17; i >= 0; i--) {
                auto tmp = extend(make_pair(l, r), i);
                if (tmp != make_pair(1, n)) {
                    ans |= 1 << i; l = tmp.first; r = tmp.second;
                }
            } if (ans == (1 << 18) - 1) printf("-1\n");
            else printf("%d\n", ans + 1);
        } return 0;
    }
} int main() {
    return QYB::main();
}