好的，这道题是 「BalticOI 2018」蠕虫之忧，我将详细解析题意、这个黄金分割搜索+随机爬山的解法。

---

一、题意理解

1. 基本模型

• 在一个 $N\times M\times K$ 的三维网格中，每个点 $(x,y,z)$ 有一个参数 $H[x,y,z]$。
• 你最多可以询问 $Q$ 次，每次询问一个点的参数值。
• 目标：找到一个局部最大值点，即该点的参数不小于它的六个相邻点（上下左右前后）的参数。
• 边界外的点参数视为 $0$。

这是一个交互题，需要设计高效的查询策略。

---

二、子任务特点分析

题目分为几个子任务：

1. 子任务1、2：$M=K=1$，即一维情况。$N=10^6$，但查询次数 $Q$ 不同：

   • 子任务1：$Q=10000$（较宽松）
   • 子任务2：$Q=35$（非常紧）

2. 子任务3、4：$K=1$，即二维情况。$N=M$ 分别为200和1000，$Q$ 分别为4000和3500。

3. 子任务5、6：三维情况。$N=M=K$ 分别为100和500，$Q$ 较多（100000和150000）。

所以代码分为两个主要解法：

• 一维情况：用黄金分割搜索（斐波那契搜索）
• 二维/三维情况：随机采样+爬山法

---

三、一维情况（黄金分割搜索）

当 $M=K=1$ 时，问题简化为一维数组找局部最大值。

1. 算法思路

在区间 $[1,N]$ 上找局部最大值。
经典的三分法可以在 $O(\log_{1.5} N)$ 次查询内找到峰值，但这里用黄金分割法（Fibonacci搜索的近似）效率更高。

黄金分割比 $\varphi = \frac{\sqrt{5}-1}{2} \approx 0.618$。

2. 代码实现

const double P = (sqrt(5.0) - 1) / 2.0;  // 黄金分割比
void Sol() {
    int L = 1, R = n;
    int x, y;
    int l = (R - L + 1) * P;
    x = R - l, y = L + l;  // 两个黄金分割点
    while (L + 1 < R) {
        l = (R - L + 1) * P;
        if (!x) x = R - l;
        if (!y) y = L + l;
        int _x = Get(x);  // 查询点x
        int _y = Get(y);  // 查询点y
        if (_x < _y)
            L = x, x = y, y = 0;  // 峰值在[x,R]中
        else
            R = y, y = x, x = 0;  // 峰值在[L,y]中
    }
    F(i, L - 2, L + 2) Get(i);  // 最后检查附近几个点
    cout << "! " << ans.x << ' ' << ans.y << ' ' << ans.z << '\n';
}

步骤：

1. 在区间 $[L,R]$ 内选两个黄金分割点 $x$ 和 $y$。
2. 查询 $H[x]$ 和 $H[y]$。
3. 如果 $H[x] < H[y]$，峰值可能在 $[x,R]$ 中，更新 $L = x$；否则峰值可能在 $[L,y]$ 中，更新 $R = y$。
4. 重复直到区间足够小。
5. 最后检查区间附近的点，确保找到局部最大值。

查询次数：

• 每次迭代查询2次，区间长度以 $\varphi$ 比例缩小。
• 对于 $N=10^6$，$2\log_{1/\varphi} N \approx 2\log_{1.618} 10^6 \approx 2\times 28.3 \approx 57$ 次。
• 但代码中 $Q=35$ 时其实会超过？这里可能是利用了边界外为0的特性，或者实际查询次数更少，因为代码最终 F(i, L-2, L+2) 会查5次附近点。

---

四、二维/三维情况（随机爬山法）

当维度大于1时，黄金分割法不再适用。这里采用随机采样+梯度上升。

1. 算法思路

void Sol2() {
    Point now = Point();
    // 随机采样 Q*0.6 次，找到当前最大值点
    F(i, 1, q * 0.6) {
        int _x = rng() % n + 1, _y = rng() % m + 1, _z = rng() % k + 1;
        int _sum = Query(Point(_x, _y, _z));
        now = max(now, Point(_x, _y, _z, _sum));
    }
    // 从该点开始爬山
    for (; ;) {
        Point _t = now;
        // 检查6个邻居
        F(i, 0, 5) {
            int _sum = Query(Point(_t.x + dx[i], _t.y + dy[i], _t.z + dz[i]));
            _t = max(_t, Point(_t.x + dx[i], _t.y + dy[i], _t.z + dz[i], _sum));
        }
        // 如果邻居都不比当前点大，则找到局部最大值
        if (_t.sum == now.sum) {
            cout << "! " << now.x << ' ' << now.y << ' ' << now.z << '\n';
            return ;
        }
        now = _t;  // 移动到更优点
    }
}

2. 步骤

1. 随机采样阶段：用 $0.6Q$ 次查询随机采样，找到参数最大的点作为爬山起点。
2. 爬山阶段：
   • 检查当前点的6个邻居。
   • 如果某个邻居参数更大，则移动到该邻居。
   • 重复直到所有邻居都不大于当前点（局部最大值）。

3. 正确性保证

• 由于参数是确定的（非随机），局部最大值一定存在。
• 随机采样大概率会落在某个局部最大值的“吸引域”内，从而爬山能到达该局部最大值。
• 在二维/三维网格中，$Q$ 足够大，可以覆盖采样和爬山的需求。

---

五、查询缓存与边界处理

1. 哈希表缓存

gp_hash_table<ull, int> mp;
ull Co(Point &_t) {
    return _t.x * 1000000llu + _t.y * 1000llu + _t.z;
}
int Query(Point x) {
    if (x.x < 1 || x.x > n || x.y < 1 || x.y > m || x.z < 1 || x.z > k)
        return 0;  // 边界外为0
    if (mp.find(Co(x)) != mp.end()) 
        return mp[Co(x)];  // 缓存命中
    // 否则查询并缓存
    cout << "? " << x.x << ' ' << x.y << ' ' << x.z << '\n';
    int _;
    cin >> x.sum;
    mp[Co(x)] = x.sum;
    return mp[Co(x)];
}

• 用哈希表缓存已查询的点，避免重复查询。
• 边界外直接返回0。

2. 数据结构

struct Point {
    int x, y, z, sum;
    // 重载<，用于max比较
    bool operator <(Point y) { return sum < y.sum; }
};

---

六、复杂度分析

一维情况

• 黄金分割：$O(\log N)$ 次查询。
• 最后检查5个点：$O(1)$。
• 总查询次数约 $2\log_{1/\varphi} N + 5 \approx 60$，但 $Q=35$ 时可能超出？实际代码可能因为边界条件提前结束。

二维/三维情况

• 随机采样：$0.6Q$ 次。
• 爬山：每次迭代查询6次邻居，但可能多次迭代。
• 总查询数控制在 $Q$ 以内。

---

七、总结

1. 一维特化：用黄金分割搜索高效找局部最大值。
2. 高维通用：随机采样+爬山法，利用大量查询次数找到局部峰值。
3. 缓存优化：避免重复查询，提高效率。
4. 边界处理：边界外参数为0，简化判断。

这个解法结合了问题特化和通用启发式策略，适应不同数据范围，是一道典型的交互优化题。