题解：CF2093D Skibidi Table

分治。

由于表格是递归定义的，所以考虑递归地查询。

查询 $(x,y)$ 的数字

递归查询。

假设当前的正方形左上角 $(a,b)$，右下角 $(c,d)$，记录当前左上角的值为 $w$。

容易得到正方形边长 $l=c-a=d-b$。

横渐近线为 $y=\dfrac{b+d}{2}$，竖渐近线为 $x=\dfrac{a+c}{2}$。

令 $t=\dfrac{l^2}{4}$，即一个小正方形的大小。

左上角 $w_1=w$。
右下角 $w_2=t+w$。
左下角 $w_3=2t+w$。
右上角 $w_4=3t+w$。

递归下去即可。

查询 $d$ 的位置

同上容易求出四个小正方形中的 $\min$ 和 $\max$。

找到 $d$ 在哪个区间中，递归下去即可。

时间复杂度

时间复杂度 $O(qn)$。

代码

Record。

#include <bits/stdc++.h>
using lint = long long;
using pll = std::pair<lint, lint>;

int T, n, q;

lint get_val(lint a, lint b, lint c, lint d, lint w, int qx, int qy) {
  lint y = b + d >> 1, x = a + c >> 1;
  lint len = c - a + 1 >> 1;
  lint t = len * len;
  if (a == c) return w;
  if (qx <= x && qy <= y) { // 左上角
    return get_val(a, b, x, y, w, qx, qy);
  } else if (qx > x && qy > y) { // 右下角
    return get_val(x + 1, y + 1, c, d, w + t, qx, qy);
  } else if (qx <= x && qy > y) { // 左下角
    return get_val(a, y + 1, x, d, w + 2 * t, qx, qy);
  } else { // 右上角
    return get_val(x + 1, b, c, y, w + 3 * t, qx, qy);
  }
}

pll get_pos(lint a, lint b, lint c, lint d, lint w, lint val) {
  lint y = b + d >> 1, x = a + c >> 1;
  lint len = c - a + 1 >> 1;
  lint t = len * len;
  if (a == c) return {a, b};
  if (val < w + t) {
    return get_pos(a, b, x, y, w, val);
  } else if (val < w + 2 * t) {
    return get_pos(x + 1, y + 1, c, d, w + t, val);
  } else if (val < w + 3 * t) {
    return get_pos(a, y + 1, x, d, w + 2 * t, val);
  } else {
    return get_pos(x + 1, b, c, y, w + 3 * t, val);
  }
}

int main() {
  std::cin.tie(0)->sync_with_stdio(0);
  for (std::cin >> T; T; --T) {
    for (std::cin >> n >> q; q; --q) {
      std::string op; std::cin >> op;
      if (op[0] == '-') {
        lint x, y; std::cin >> x >> y;
        std::cout << get_val(1, 1, 1ll << n, 1ll << n, 1, y, x) << "\n";
      } else {
        lint d; std::cin >> d;
        auto ans = get_pos(1, 1, 1ll << n, 1ll << n, 1, d);
        std::cout << ans.second << " " << ans.first << "\n";
      }
    }
  }
  std::cout.flush();
  return 0;
}