题解

思路概述

• 题面允许我们询问三个位置的中位数。只要掌握“当前最小的两个值”和“当前最大的两个值”，就能用一问把第 $m$ 个数分类：用一个“偏大”的代表和一个“偏小”的代表与新位置组成查询，中位数小于现有的“低端”阈值说明新数更小；中位数大于“高端”阈值说明更大；否则新数落在中间（我们直接输出它的值）。
• 首先对前四个位置做四次询问，得到四个三元组的中位数。最小的中位数对应两个最小值所在的位置，最大的中位数对应两个最大值所在的位置。把它们分别记作 (i,j) 与 (k,l) 并记录对应的中位数 x、y，其中 x 是“低端哨兵”的值，y 是“高端哨兵”的值。
• 之后依次处理第 m (≥5) 个位置：询问 ask(i, k, m)。
  • 若结果小于 x，说明 a_m 比当前最小值还小，于是原来的“低端第二小”j 已经确定，它的值就是旧的 x，输出后用m替换 j。
  • 若结果等于 x，则原来的 i 可以确定，其值即 x。随后重新用 ask(i, j, m)（此时 i 还是旧的哨兵）得到新的 x，并把 i 更新为 m 充当新的“低端代表”。
  • 同理，若结果大于 y 或等于 y，就处理“高端”两位 (k,l)。
  • 如果落在 x 与 y 之间，则直接输出当前位置的值（因为三数中位数就是它本身）。
• 这样每加入一个新位置都会确定并输出至少一个旧位置的数值；当新数位于两哨兵之间时，我们也能立即输出它本身，因此总询问次数为 $O(n)$。

实现细节

• answer(x, v) 在确定下标 x 的真实值后立即调用；每个下标最多输出一次，符合题面限制。
• 维护的四个位置 (i,j,k,l) 始终互不相同。由于每次只做常数次 ask 操作，整体询问次数与常数因子都较小。
• 当 N < 4 时无法构造这样的哨兵，题解中直接返回，此时交互库不会要求输出具体答案。

复杂度

仅做常数次预处理询问，再对每个后续位置执行常数次 ask，故总询问次数与时间复杂度均为 $O(n)`。

#include "guess.h"

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")



void guess(int N) {
  if (N < 4) return;
  
  // max{a[i], a[j]} = x < y = max{a[k], a[l]}
  int x, y;
  int i, j, k, l;
  {
    int zs[5];
    zs[1] = ask(2, 3, 4);
    zs[2] = ask(1, 3, 4);
    zs[3] = ask(1, 2, 4);
    zs[4] = ask(1, 2, 3);
    x = *min_element(zs + 1, zs + 5);
    y = *max_element(zs + 1, zs + 5);
    for (i = 1    ; i <= 4; ++i) if (y == zs[i]) break;
    for (j = i + 1; j <= 4; ++j) if (y == zs[j]) break;
    for (k = 1    ; k <= 4; ++k) if (x == zs[k]) break;
    for (l = k + 1; l <= 4; ++l) if (x == zs[l]) break;
// cerr<<x<<" "<<y<<"; "<<i<<" "<<j<<" "<<k<<" "<<l<<"; zs = ";pv(zs+1,zs+5);
  }
  for (int m = 5; m <= N; ++m) {
    const int z = ask(i, k, m);
    if (z < x) {
      answer(j, x);
      x = z;
      j = m;
    } else if (z == x) {
      answer(i, x);
      x = ask(i, j, m);
      i = m;
    } else if (y < z) {
      answer(l, y);
      y = z;
      l = m;
    } else if (y == z) {
      answer(k, y);
      y = ask(k, l, m);
      k = m;
    } else {
      answer(m, z);
    }
// cerr<<x<<" "<<y<<"; "<<i<<" "<<j<<" "<<k<<" "<<l<<endl;
  }
}