题目大意

交互库有一个隐藏的 $1 \sim n$ 的排列 $a_1, a_2, \dots, a_n$，以及一个初始值 $x$。你每次可以询问位置 $i$，交互库会比较 $a_i$ 与当前 $x$ 的大小关系并返回 >、< 或 =，同时 $x$ 会相应变化：

• 若 $a_i > x$，返回 >，$x \leftarrow x + 1$；
• 若 $a_i < x$，返回 <，$x \leftarrow x - 1$；
• 若 $a_i = x$，返回 =，$x$ 不变。

你需要在不超过 $40n$ 次询问内猜出整个排列。

核心思想

本题的核心是利用两个已知元素——值为 $1$ 和值为 $n$ 的位置——作为“调节 $x$ 的工具”。询问值为 $1$ 的位置永远会返回 <（只要 $x > 1$）并使 $x$ 减 $1$；询问值为 $n$ 的位置永远会返回 >（只要 $x < n$）并使 $x$ 加 $1$。借助这两个“锚点”，我们可以将 $x$ 任意调整到某个目标值，并在分治过程中保持 $x$ 稳定。

整个解法分为三个阶段：

1. 找到值为 $1$ 的位置 pos1；
2. 找到值为 $n$ 的位置 posn；
3. 分治确定所有位置的值。

第一步：寻找 $1$ 的位置

我们不知道初始 $x$ 是多少，但通过遍历所有位置，可以使 $x$ 逐渐减小，最终锁定值为 $1$ 的位置。标程中的循环如下：

int pos1 = -1;
for (int i = 1; i <= n; ++i) {
    char ans = query(i);
    if (ans == '<') {
        --i;                // 重复询问同一位置
    } else if (ans == '=') {
        pos1 = i;
    } else {                // ans == '>'
        if (pos1 != -1)
            query(pos1);
    }
}

逻辑解释：

• 当返回 < 时，说明 $a_i < x$，$x$ 自动减 $1$。此时我们让 i 减 $1$，使得下一次循环再次询问同一个 $i$，直到返回值不再是 < 为止。这一步会将 $x$ 持续降低，直到 $x \le a_i$。
• 当返回 = 时，说明 $a_i = x$，我们记录下该位置 pos1，并继续向后遍历。
• 当返回 > 时，说明 $a_i > x$，$x$ 加 $1$。如果此前已经找到过 pos1，我们就额外询问一次 pos1。由于 pos1 的值是当时 $x$ 的值，而现在 $x$ 可能已经变大，询问 pos1 大概率会返回 <，从而将 $x$ 拉低，帮助我们在后续遇到更小值时能更快下降。

最终，$x$ 会变成 $1$（因为排列中必然有 $1$），且 pos1 就是值为 $1$ 的那个位置。

第二步：寻找 $n$ 的位置

与第一步对称，这次我们要让 $x$ 上升到 $n$，并记录值为 $n$ 的位置。

int posn = -1;
for (int i = 1; i <= n; ++i) {
    char ans = query(i);
    if (ans == '>') {
        --i;
    } else if (ans == '=') {
        posn = i;
    } else {                // ans == '<'
        if (posn != -1)
            query(posn);
    }
}

循环结束后，posn 即为值为 $n$ 的位置，且此时 $x = n$。

第三步：分治确定所有值

现在我们有了两个“调节器”：pos1（询问必减 $1$）和 posn（询问必加 $1$），并且当前 $x = n$。接下来使用分治算法，每次将值域 $[l, r]$ 折半，用中位数 $m$ 来测试待定的位置。

初始调整

分治前，我们需要把 $x$ 调整到整个值域的中位数 $m = \lfloor \frac{1+n}{2} \rfloor$。由于当前 $x = n$，我们执行 $n - m$ 次 query(pos1)，每次使 $x$ 减 $1$，最终 $x = m$。

递归分治函数 dnq(l, r, pos, res, pos1, posn)

参数：

• l, r：当前值域区间；
• pos：所有尚未确定值的下标集合（这些位置的值保证在 $[l, r]$ 内）；
• res：结果数组；
• pos1, posn：值为 $1$ 和 $n$ 的位置。

函数流程：

1. 取中位数 $m = \lfloor \frac{l+r}{2} \rfloor$。
2. 遍历 pos 中的每个下标 $i$，询问 query(i)：
   • 若返回 >：说明 $a_i > x$（当前 $x = m$），因此 $a_i \in [m+1, r]$，将其放入右侧集合 rh。同时 $x$ 会加 $1$，我们立刻 query(pos1) 让 $x$ 减 $1$，从而抵消影响，保持 $x = m$。
   • 若返回 <：说明 $a_i < x$，因此 $a_i \in [l, m-1]$，放入左侧集合 lh。同时 query(posn) 抵消 $x$ 的减少，保持 $x = m$。
   • 若返回 =：说明 $a_i = m$，直接记录 res[i] = m。
3. 递归处理左侧：
   • 若 lh 非空，需要将 $x$ 从 $m$ 调整到左区间的中位数 $m_2 = \lfloor \frac{l+m-1}{2} \rfloor$。执行 $(m - m_2)$ 次 query(pos1)，使 $x$ 降低到 $m_2$。
   • 调用 dnq(l, m-1, lh, res, pos1, posn)。
   • 递归返回后，调用一次 query(posn)。这一步与右侧的调整协同，为后续恢复 $x$ 或进入右侧分支做准备。
4. 递归处理右侧：
   • 若 rh 非空，需要将 $x$ 调整到右区间的中位数 $m_2' = \lfloor \frac{m+1+r}{2} \rfloor$。执行 $(m_2' - m)$ 次 query(posn)，使 $x$ 提升到 $m_2'$。
   • 调用 dnq(m+1, r, rh, res, pos1, posn)。

这样，每一层递归中每个位置恰好被询问一次（外加一些调整用的询问），最终所有位置的值都被确定。

输出答案

最后输出 ! 以及排列 $a_1, a_2, \dots, a_n$。

复杂度分析

• 寻找 $1$ 和 $n$ 的过程：每个位置可能被询问多次，但总询问次数仍然是 $O(n)$ 级别。
• 分治过程：每一层递归中，每个未确定的位置被询问一次，并伴随常数次调节询问。递归深度为 $O(\log n)$，因此总询问次数为 $O(n \log n)$。由于 $n \le 2000$，$n \log n \approx 2000 \times 11 = 22000$，远小于限制的 $40n = 80000$，足够通过。

完整代码（附注释）

#include <bits/stdc++.h>
using namespace std;

char query(int pos) {
    cout << "? " << pos << endl;
    char ans;
    cin >> ans;
    return ans;
}

void dnq(int l, int r, vector<int> pos, vector<int>& res, int pos1, int posn) {
    int m = (l + r) / 2;                // 当前区间的中位数
    vector<int> lh, rh;                 // 分到左右子区间的下标
    for (int i = 0; i < pos.size(); ++i) {
        char x = query(pos[i]);
        if (x == '>') {
            rh.push_back(pos[i]);       // a[i] > m
            query(pos1);                // 抵消 x 的增加
        } else if (x == '<') {
            lh.push_back(pos[i]);       // a[i] < m
            query(posn);                // 抵消 x 的减少
        } else {
            res[pos[i]] = m;            // a[i] == m
        }
    }
    // 处理左侧
    if (!lh.empty()) {
        int m2 = (l + m - 1) / 2;
        for (int j = 0; j < m - m2; ++j)   // 将 x 降到 m2
            query(pos1);
        dnq(l, m - 1, lh, res, pos1, posn);
        query(posn);                        // 配合右侧调整
    }
    // 处理右侧
    if (!rh.empty()) {
        int m2 = (m + 1 + r) / 2;
        for (int j = 0; j < m2 - m; ++j)    // 将 x 升到 m2
            query(posn);
        dnq(m + 1, r, rh, res, pos1, posn);
    }
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;

        // 第一步：找值为 1 的位置
        int pos1 = -1;
        for (int i = 1; i <= n; ++i) {
            char ans = query(i);
            if (ans == '<') {
                --i;
            } else if (ans == '=') {
                pos1 = i;
            } else {
                if (pos1 != -1) query(pos1);
            }
        }

        // 第二步：找值为 n 的位置
        int posn = -1;
        for (int i = 1; i <= n; ++i) {
            char ans = query(i);
            if (ans == '>') {
                --i;
            } else if (ans == '=') {
                posn = i;
            } else {
                if (posn != -1) query(posn);
            }
        }

        // 第三步：分治确定排列
        vector<int> res(n + 1);
        vector<int> pos(n);
        for (int j = 0; j < n; ++j) pos[j] = j + 1;

        int m = (1 + n) / 2;
        for (int k = 0; k < n - m; ++k)    // 将 x 从 n 调整到 m
            query(pos1);

        dnq(1, n, pos, res, pos1, posn);

        cout << "! ";
        for (int j = 1; j <= n; ++j)
            cout << res[j] << ' ';
        cout << endl;
    }
    return 0;
}

总结

本题巧妙利用了两个确定值（$1$ 和 $n$）作为 $x$ 的“升降机”，在分治过程中始终保持 $x$ 为当前区间中位数，从而将问题转化为标准的比较二分过程。整体询问次数控制在 $O(n \log n)$，完美满足题目要求。