题面

题意

交互题。

交互库在开始时会生成一个长为 $n$ 的排列 $p$。你在开始时仅知道排列的长度 $n$，你需要在进行不超过 $\lfloor \frac {3 \times n} 2 \rfloor + 30$ 次询问后输出这个排列。

你可以进行两种类型的提问：

1. ? 1 i j x： 交互库会告诉你 $\max(\min(x,p_i),\min(x+1,p_j))$ 的值。
2. ? 2 i j x： 交互库会告诉你 $\min(\max(x,p_i),\max(x+1,p_j))$ 的值。

分析

我们考虑指定 $i,~j,~x$ 后所有可能的情况下的询问结果，为了方便归类，下面忽略了相等的情况。

1. $p_i >x,~p_j>x+1$： $1$ 询问返回 $x+1$，$2$ 询问返回 $\min(p_i,p_j)$。
2. $p_i>x,~p_j<x+1$： $1$ 询问返回 $x$，$2$ 询问返回 $x+1$。
3. $p_i<x,~p_j>x+1$： $1$ 询问返回 $x+1$，$2$ 询问返回 $x$。
4. $p_i<x,~p_j<x+1$： $1$ 询问返回 $\max(p_i,p_j)$，$2$ 询问返回 $x$。

我们发现这四种情况中仅 $1$ 情况的 $2$ 询问，和 $4$ 情况的 $1$ 询问返回的值与 $p$ 相关，我们考虑从此处入手。

由于我们需要得知具体的 $p$ 中的每一个元素的值，考虑可以对两个元素同时进行 $1$ 情况的 $2$ 询问和 $4$ 情况的 $1$ 询问，以得到这两个元素中的较大值和较小值，但无法确定这两个值具体对应的位置。接着可以再通过 $2$ 情况和 $3$ 情况下的询问确定这两个元素的具体大小关系，就可以确定这两个位置上分别的值。

具体地，我们可以先考虑将 $n$ 长度的排列两两分组，如果 $n$ 为奇数则先忽略最后一个元素。对于每组内的两个元素：

1. 询问 ? 2 i j 1，在大部分情况下 $p_i\ge1,~p_j\ge2$，可以对应 $1$ 情况，得到 $\min(p_i,p_j)$；当 $p_j=1$ 时该询问会对应 $2$ 情况，返回 $2$。我们可以对于所有返回值为 $2$ 的情况再询问 ? 1 i j 1，若返回值为 $2$ 则确认对应 $1$ 情况，$\min(p_i,p_j)=2$；否则返回值一定为 $1$，确认对应 $2$ 情况，$p_j=1$。
2. 询问 ? 1 i j n-1，在大部分情况下 $p_i \le n-1,~p_j \le n$，可以对应 $4$ 情况，得到 $\max(p_i,p_j)$；当 $p_i=n$ 时该询问会对应 $2$ 情况，返回 $n-1$。我们可以对于所有返回值为 $n-1$ 的情况再询问 ? 2 i j n-1，若返回值为 $n-1$ 则确认对应 $4$ 情况，$\max(p_i,p_j)=n-1$；否则返回值一定为 $n$，确认对应 $2$ 情况，$p_i=n$。
3. 询问 ? 1 i j min(p[i],p[j])，若返回值为 $\min(p_i,p_j)$ 则说明对应 $2$ 情况，$p_i > \min(p_i,p_j),~p_j<\min(p_i,p_j)+1$，所以 $p_i>p_j$；否则返回值一定为 $\min(p_i,p_j)+1$，对应 $3$ 情况，$p_i<\min(p_i,p_j),~p_j>\min(p_i,p_j)+1$，所以 $p_i < p_j$。（由于忽略了相等的情况所以式子可能不成立，但是足以判断两个元素的大小关系了）
4. 对于上一步中得到的 $p_i$ 与 $p_j$ 的大小关系，和之前得到的 $\min(p_i,p_j),~\max(p_i,p_j)$，得到 $p_i,~p_j$ 的值。

对于 $n$ 为奇数的情况，在前 $n-1$ 个元素的值被求出后，找到那个没有被求出过的值赋值到 $p[n]$ 即可。

对于每两个元素我们进行了大约三次操作，且步骤 $1$ 和步骤 $2$ 中用于检验的询问次数相当少，所以总操作次数大约为 $\lfloor \frac {3 \times n} 2 \rfloor$，可以通过本题。

代码

如果上面的解释看懵了，也许可以尝试看一下代码。

代码比解释清楚多了

/**
 * @author Macesuted (macesuted@qq.com)
 * @copyright Copyright (c) 2021
 */

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

int ask1(int i, int j, int p) {
    cout << "? 1 " << i << ' ' << j << ' ' << p << endl;
    int ret;
    cin >> ret;
    return ret;
}
int ask2(int i, int j, int p) {
    cout << "? 2 " << i << ' ' << j << ' ' << p << endl;
    int ret;
    cin >> ret;
    return ret;
}

int p[10005];
bool vis[10005];

int main() {
    ios::sync_with_stdio(false);
    int _;
    cin >> _;
    while (_--) {
        int n;
        cin >> n;
        for (register int i = 1; i <= n; i++) vis[i] = false;
        for (register int i = 1; i < n; i += 2) {
            int ret = ask1(i, i + 1, n - 1);
            p[i] = (ret == n - 1 && ask2(i, i + 1, n - 1) == n) ? n : ret;
            ret = ask2(i, i + 1, 1);
            p[i + 1] = (ret == 2 && ask1(i, i + 1, 1) == 1) ? 1 : ret;
            if (ask1(i, i + 1, p[i + 1]) == p[i + 1] + 1) swap(p[i], p[i + 1]);
            vis[p[i]] = vis[p[i + 1]] = true;
        }
        if (n & 1)
            for (register int i = 1; i <= n; i++)
                if (!vis[i]) p[n] = i;
        cout << '!';
        for (register int i = 1; i <= n; i++) cout << ' ' << p[i];
        cout << endl;
    }
    return 0;
}