分治。

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

查询 (x,y) 的数字

递归查询。

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

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

横渐近线为 ，竖渐近线为 。

令 ，即一个小正方形的大小。

  • 左上角 w1 = w。
  • 右下角 w2 = t + w。
  • 左下角 w3 = 2t + w。
  • 右上角 w4 = 3t + w。

递归下去即可。

查询 d 的位置

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

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

时间复杂度

时间复杂度 O(qn)。

代码

Record。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#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;
}