题解：P9683 A Certain Forbidden Index

· · 题解

题目传送门

P9683 A Certain Forbidden Index

题目大意

我们一共有 2^k 个点，这些点构成一颗完整的线段树，有一个我们未知的节点被标记了，我们要通过询问一段区间内的节点是否有被标记的点，来推出这个被标记的节点左右端点，即这个节点维护的对应的是原序列的哪段区间。

思路简述

我们首先要模拟一下一颗完整线段树的建树过程，叶子节点的维护的原序列的长度为1，这是显然的。

我们接下来就可以自然而然的想到，如果我们定义叶子节点的深度为0的话，若这颗线段树一共有n层，那么根节点的在原序列对应的长度 2^{n-1} ，用题目中的k来表示就是 2^{k} 的长度。

基于每一层的每一个节点维护的在原序列中的长度，我们充分发扬类人智慧，我们可以显然的发现，如果我们将线段树每一层的节点从0开始设置编号，那么我们就可以按照每一层节点对应编号的奇偶性进行分类讨论。

另外，我们需要注意的是，我们需要从叶子节点的上一层进开始行奇偶性的设置和判断，叶子节点再单独判断。要不然会有的叶子节点不会被询问覆盖掉，我们要考虑的是用最少的询问覆盖掉所有的线段树节点，这样就能确定被标记的节点的位置。还有，如果我们从叶子节点开始设计询问的话，就无法做到从0开始编号，进而无法利用奇偶性来进行讨论的下一步的询问。

我们可以想到，如果我们固定一个区间的左端点l，那么我们就可以一次询问四个区间（具体看代码即可），左边的孤点，右边的孤点，以及中间的两个具有两个完整该层单块长度的线段树区间，这样就可以完整的探测出所有线段树节点。

还有一个需要注意的点就是，最后还需要判断一下，叶子节点的最左和最右，以及根节点是否被标记。

Coding

#include <bits/stdc++.h>
using std :: cin; using std :: cout;
using std :: min; using std :: max;

int query(int, int);

#define LL long long

std::pair<int, int> solve(int k) {

    LL n = (1 << k);

    for (int i = 1; i < k; ++ i) {
        LL len = 1 << i;
        for (int l = 1; l <= n; l += len) {
            int r = l + len - 1;
            int idx = (l >> i);
            if (idx & 1) [[likely]] {
                if (r == n) {
                    if (query(l - 1, r)) {
                        if (query(l - 1, l - 1)) [[likely]] return { l - 1, l - 1 };
                        return { l, r };
                    }
                } else {
                    if (query(l - 1, r + len + 1)) [[likely]] {
                        if (query(l - 1, l - 1)) [[likely]] return { l - 1, l - 1 };
                        if (query(l, r)) [[likely]] return {l, r};
                        if (query(r + 1, r + len)) [[likely]] return { r + 1, r + len };
                        return { r + len + 1, r + len + 1 };
                    }
                }
            } else {
                if (l == 1) [[likely]] {
                    if (query(l, r + 1)) [[likely]] {
                        if (query(r + 1, r + 1)) return { r + 1, r + 1 };
                        return { l, r };
                    }
                }
            }
        }
    }

    if (query(1, 1)) [[likely]] return { 1, 1 };
    if (query(n, n)) [[likely]] return { n, n };

    return { 1, n };
}