QOJ #2373. Find the Array 题解

Description

给定一个长度为 $n$ 的数组 $a$，数组中的元素互不相同。保证每个元素都是不超过 $10^9$ 的正整数。
你的任务是找出数组中所有元素的值。

为此，你可以最多进行 30 次查询，查询有两种类型：

• $1\ i$ $(1 \leq i \leq n)$ —— 询问数组中第 $i$ 个元素的值 $a_i$。

• $2\ k\ i_1, i_2, \ldots, i_k$ $(2 \leq k \leq n,\; 1 \leq i_j \leq n,\; 所有 \; i_j \; 必须互不相同)$ —— 输入数字 $k$ 和数组中的 $k$ 个位置。

  作为该查询的回答，你会得到 $\frac{k \cdot (k-1)}{2}$ 个整数——它们是所有满足 $c < d$ 的下标对对应的差值绝对值：$|a_{i_c} - a_{i_d}|$。

  换句话说，你会得到所选 $k$ 个元素的所有两两绝对差值。注意，返回的结果会被随机打乱顺序。

当你已经确定整个数组 $a$ 后，你需要使用以下查询输出答案：

• $3\ a_1, a_2, \ldots, a_n$ $(1 \leq a_i \leq 10^9)$ —— 输出数组的所有元素。
  执行此查询后，你的程序必须终止。
  这个查询 不计入 30 次查询限制（即你可以进行至多 30 次类型 1 或类型 2 的查询，然后再进行 1 次类型 3 的查询）。

$n\leq 250$。

Solution

首先这类查询两两之间的差值再还原序列的题有个很普遍的技巧是找到全局的最大值或者最小值，再得到每个数与这个极值的距离后就能还原序列。

这题也考虑这么做。

第一步要找到极值。可以先用一次查询得到全局的极差，然后二分找到最小的 $p$，使得前缀 $[1,p]$ 的极差等于全局极差，那么最小的 $p$ 就一定是最小值或者最大值。这部分操作数是 $\lceil\log_2 n\rceil+1$。

设 $b_i$ 表示 $|a_i-a_p|$，然后能够发现我们通过查询 $S$ 和 $S\cup\{p\}$，再将两个结果集合相减可以得到 $S$ 中下标的 $b$ 数组的无序集合，设其为 $f(S)$。

得到有序集合有个做法是假设当前的集合为 $S$，先把 $S$ 划分成 $S_1$ 和 $S_2$，得到 $f(S_1)$ 后，$f(S_2)$ 就是 $f(S)\setminus f(S_1)$，再分治下去即可。

不过这么做是 $O(n)$ 次的，但是我们可以整层一起分治。具体地，假设当前层的分治集合是 $S_1,S_2,\ldots,S_k$，先得到 $T$ 为所有这些集合分别 $1$ 号集合的并，那么 $f(S_{i,1})=f(T)\cap f(S_i),f(S_{i,2})=f(S_i)\setminus f(S_{i,1})$。按照类似线段树的方式进行分治即可。

单层的询问次数是 $2$，总次数就是 $2\lceil\log_2 n\rceil$。

得到 $b_i$ 后用 $1$ 操作得到 $a_p$ 以及任意一个其余数的具体值即可得到所有数的具体值。

总次数是 $3\lceil\log_2 n\rceil+5$。

Code

#include <bits/stdc++.h>

// #define int int64_t

using vi = std::vector<int>;

const int kMaxN = 255;

int n, pos;
int L[kMaxN * 4], R[kMaxN * 4], dep[kMaxN * 4], b[kMaxN], res[kMaxN];
vi vec[kMaxN * 4], vid[10];

int getval(int x) {
  std::cout << "1 " << x << '\n';
  fflush(stdout);
  int v;
  std::cin >> v;
  return v;
}

vi query(vi vec) {
  if (vec.size() <= 1) return {};
  std::cout << "2 " << vec.size() << ' ';
  for (auto i : vec) std::cout << i << ' ';
  std::cout << '\n';
  fflush(stdout);
  vi vv(vec.size() * (vec.size() - 1) / 2);
  for (auto &x : vv) std::cin >> x;
  std::sort(vv.begin(), vv.end());
  return vv;
}

int getpos() {
  int L = 1, R = n, res = n, mx = 0;
  vi vec;
  for (int i = 1; i <= n; ++i) vec.emplace_back(i);
  auto vv = query(vec);
  mx = vv.back();
  while (L + 1 < R) {
    int mid = (L + R) >> 1;
    vi vec;
    for (int i = 1; i <= mid; ++i) vec.emplace_back(i);
    auto ret = query(vec);
    if (ret.back() == mx) R = res = mid;
    else L = mid;
  }
  return res;
}

void build(int x, int l, int r) {
  L[x] = l, R[x] = r, dep[x] = dep[x >> 1] + 1;
  vid[dep[x]].emplace_back(x);
  if (l != r) {
    int mid = (l + r) >> 1;
    build(x << 1, l, mid), build(x << 1 | 1, mid + 1, r);
  }
}

vi operator &(vi a, vi b) {
  vi ret;
  std::unordered_map<int, int> mp;
  for (auto x : a) ++mp[x];
  for (auto x : b)
    if (mp[x]) ret.emplace_back(x), --mp[x];
  return ret;
}

vi operator ^(vi a, vi b) {
  vi ret;
  std::unordered_map<int, int> mp;
  for (auto x : a) ++mp[x];
  for (auto x : b) --mp[x];
  for (auto [x, v] : mp) {
    assert(v >= 0);
    for (int i = 1; i <= v; ++i)
      ret.emplace_back(x);
  }
  return ret;
}

vi getb(std::vector<int> vec) {
  std::vector<int> _v;
  for (auto x : vec)
    if (x != pos)
      _v.emplace_back(x);
  if (vec.size() == _v.size()) {
    _v.emplace_back(pos);
    vi a = query(vec), b = query(_v);
    return b ^ a;
  } else {
    vi ret = getb(_v);
    ret.emplace_back(0);
    return ret;
  }
}

void dickdreamer() {
  std::cin >> n;
  if (n == 1) {
    int v = getval(1);
    std::cout << "3 " << v << '\n';
    return;
  }
  pos = getpos();
  build(1, 1, n);
  vi vv;
  for (int i = 1; i <= n; ++i) vv.emplace_back(i);
  vec[1] = getb(vv);
  for (int i = 1; i <= 9; ++i) {
    vi vec;
    for (auto x : vid[i]) {
      int l = L[x], r = R[x], mid = (l + r) >> 1;
      if (l != r) {
        for (int j = l; j <= mid; ++j) vec.emplace_back(j);
      }
    }
    if (!vec.size()) break;
    vi vl = getb(vec);
    for (auto x : vid[i]) {
      if (L[x] != R[x]) {
        ::vec[x << 1] = ::vec[x] & vl;
        ::vec[x << 1 | 1] = ::vec[x] ^ ::vec[x << 1];
      }
    }
  }
  for (int i = 1; i <= n * 4; ++i) {
    if (L[i] && R[i]) {
      assert(vec[i].size() == R[i] - L[i] + 1);
      if (L[i] == R[i]) b[L[i]] = vec[i][0];
    }
  }
  int pp = (pos == 1 ? 2 : 1), v1 = getval(pos), v2 = getval(pp);
  // std::cerr << "fuck " << b[1] << ' ' << b[2] << ' ' << b[3] << '\n';
  if (v1 < v2) {
    for (int i = 1; i <= n; ++i) res[i] = v1 + b[i];
  } else {
    for (int i = 1; i <= n; ++i) res[i] = v1 - b[i];
  }
  std::cout << "3 ";
  for (int i = 1; i <= n; ++i) std::cout << res[i] << " \n"[i == n];
  fflush(stdout);
}

int32_t main() {
// #ifdef ORZXKR
//   freopen("in.txt", "r", stdin);
//   freopen("out.txt", "w", stdout);
// #endif
//   std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}