题目传送门

Solution

三档分啊，看起来要三种算法，但是二维的可以用三维的随机化过掉。

首先看到一维的这个东西，想到一个类似三分的东西是容易的：要在 $[l,r]$ 找到这个点，可以比较 $a_{m_1}$ 和 $a_{m_2}$，若 $a_{m_1}\le a_{m_2}$，则可以在 $[m_1+1,r]$ 继续找，否则可以在 $[l,m_2-1]$ 继续找。这个算法的原理在于题目只要我们找到一个局部峰值而不是全局峰值。

然后这个 $m_1$ 和 $m_2$ 你一般取是过不了的，因为询问次数限制 $Q=35$，$n=10^6$，普通三分要 $40$ 次左右。这里介绍一个关于三分的技巧：

如果题目是交互题卡你三分次数，或者三分的 check 代价比较大，普通三分是不够的，此时的 $m_1$ 和 $m_2$ 取到的值非常关键，我们可以取黄金比，即 $m_1=\phi\times l+(1-\phi)\times r$，$m_2=\phi\times r+(1-\phi)\times l$，$\phi$ 是黄金比即 $\frac{\sqrt5-1}2$，这样你会惊奇的发现，由于黄金比的特性，在下一层中，$f(m_1)$ 和 $f(m_2)$ 中有一个是被算过的，这样可以大大减少调用 $f$ 的次数。正常三分的次数在 $2\log_2n$ 左右，而用这种算法大概是 $\log_\frac1\phi n=\log_{1+\phi}n$。还有一个就是精度问题，导致有的时候不能精准调用已经算过的 $f$，这个细节可以看代码。这样就可以将询问次数降到 $29$，这个 $35$ 有点松了。

这个二维可以去看官解，反正我是没看懂，写的一坨，我直接用三维的方法过掉了。

这个三维的情况就很棘手，这时候只能祭出我们的随机化了！

直接随机询问选最大的点是不行的。容易想到爬山法：选个点然后询问周围 $6$ 个点，往大的地方走，这个也是不行的。那么，这两个算法结合起来是不是就可以了？

设 $C=n\times m\times k$ 即总点数，从中随机选 $r$ 个点，选出最大的那个，然后爬山法，$Q$ 为限制的询问次数。

这个东西的正确率也是很玄学啊，首先确定爬山法能爬几下，乍一看爬一下需要 $6$ 次询问，但会有重复询问一个点的地方，不过我们先不管，就算满这个 $6$ 次，由于每爬一次权值至少会变大 $1$，排名也会上升，所以排名最少上升 $\frac{Q-r}{6}$，实际会多很多，故我们只需要在随机 $r$ 次时随到排名前 $\frac{Q-r}{6}$ 的点就可以找到答案！失败的概率为：$(1-\frac{Q-r}{6C})^r$。

最小化这个东西，问下 AI 或者放进 Desmos，发现当 $r$ 是整数时，$r\in\{\lfloor\frac Q2\rfloor,\lceil\frac Q2\rceil\}$ 时最小（这两种情况相差太小，而且 $Q$ 为偶数，在这题不重要），直接 $r=\frac Q2$ 即可。

此时失败的概率是 $(1-\frac Q{12C})^\frac Q2$，代入 $C=500^3=1.25\times10^8$ 和 $Q=150000$，算出来失败的概率是 $0.00055287698857$，约为 $\frac1{1808}$。

而且这个完全没有算满，比如爬一次平均不需要 $6$ 次，而且这个爬山法由于起点随机，很不好卡，这个 $\frac{Q-r}6$ 可能会变大很多。

我的 AC 记录，最大的询问次数为 $84706$，减去随机的 $\frac{Q}2$ 后爬山次数只有 $9706$！将 $\frac Q{12C}$ 的 $12$ 换成其他数字后的失败概率如下：

把二维的 $C=10^6$ 和 $Q=3500$ 代入，注意二维情况下 $12$ 要换成 $8$，算出来失败概率竟然有 $0.464965286284$！以下是将 $8$ 换成其他数字后的失败概率：

可以看到失败概率还是比较大的，我交了 $14$ 发，这个 sub 过了 $4$ 次（我的提交里的 78pts 和 100pts 都是过了这个 sub 的，78pts 是因为一维的写挂了），这个东西官解好像是有确定性做法的，但写的太史了，我没看懂。

Code

if (q == 35) {
    int l = 1, r = n, x = round($ * l + (1 - $) * r), y = round($ * r + (1 - $) * l);
    while (l < r)
        if (ask(x, 1, 1) > ask(y, 1, 1)) r = y - 1, swap(x, y = round($ * l + (1 - $) * r));
        else l = x + 1, swap(x = round($ * r + (1 - $) * l), y);
    cout << "! " << l << " 1 1" << endl;
} else {
    int mx = 0, X, Y, Z, x, y, z;
    while (cnt << 1 < q) {
        x = rnd() % n + 1, y = rnd() % m + 1, z = rnd() % k + 1;
        if (ask(x, y, z) > mx) mx = ask(x, y, z), X = x, Y = y, Z = z;
    }
    vector<int> p{1, 2, 3, 4, 5, 6};
    while (cnt < q) {
        for (int i = 1; i < 6; ++i) swap(p[i], p[rnd() % i]);
        x = 0;
        for (auto i : p) {
            if (cnt == q) break;
            if (i == 1) if (X < n && ask(X + 1, Y, Z) > ask(X, Y, Z)) { ++X, x = 1; break; }
            if (i == 2) if (X > 1 && ask(X - 1, Y, Z) > ask(X, Y, Z)) { --X, x = 1; break; }
            if (i == 3) if (Y < m && ask(X, Y + 1, Z) > ask(X, Y, Z)) { ++Y, x = 1; break; }
            if (i == 4) if (Y > 1 && ask(X, Y - 1, Z) > ask(X, Y, Z)) { --Y, x = 1; break; }
            if (i == 5) if (Z < k && ask(X, Y, Z + 1) > ask(X, Y, Z)) { ++Z, x = 1; break; }
            if (i == 6) if (Z > 1 && ask(X, Y, Z - 1) > ask(X, Y, Z)) { --Z, x = 1; break; }
        }
        if (!x) return cout << "! " << X << ' ' << Y << ' ' << Z << endl, 0;
    }
}