CF1521C Nastia and a Hidden Permutation

真是个沙比提，比赛的时候也想出来了，但是因为太迷糊了没写完

首先我们先考虑如何确定下最大值所在的位置。

执行询问$max(min(n-1,p_i),min(n,p_{i+1}))$，这个询问实际上等价于$max(min(n-1,p_i),p_{i+1})$。

• 如果结果是n，那么说明$p_{i+1}=n$（很显然，max里第一项不会超过n-1）。
• 如果结果比n-1要小，那么说明$p_i$和$p_{i+1}$都不是n。
• 如果结果是n-1，那么就要讨论下了。这个时候n可能出现在这两个数里，也可能没出现。

我们再构造另一个询问：$min(max(n-1,p_i),max(n,p_{i+1}))$，显然这个询问等价于$max(n-1,p_i)$，所以我们可以利用这个询问来检查$p_i$的值是不是n。

在找到最大值的位置，设它为$maxpos$，那么我们对于每一个$i\neq maxpos$，构造询问$min(max(1,p_i),max(2,p_{maxpos}))$，这个询问等价于$p_i$，然后就可以求出来每个位置的值了。

#include <algorithm>
#include <iostream>
using std::cin;
using std::cout;
using std::endl;
using int_t = long long;
int_t result[int_t(1e5)];
int main() {
    std::ios::sync_with_stdio(false);
    int_t T;
    cin >> T;
    while (T--) {
        int_t n;
        cin >> n;
        int_t maxpos = -1;
        const auto check = [&](int_t i, int_t j) {
            cout << "? 1 " << i << " " << j << " " << n - 1 << endl;
            int_t x;
            cin >> x;
            if (x == n) {
                maxpos = j;
                return;
            }
            if (x < n - 1)
                return;
            // x==n-1
            for (int_t _ = 1; _ <= 2; _++) {
                cout << "? 2 " << i << " " << j << " "<< n - 1 << endl;
                cin >> x;
                if (x == n) {
                    maxpos = i;
                }
                std::swap(i, j);
            }
        };
        for (int_t i = 1; i <= n && i + 1 <= n && maxpos == -1; i += 2) {
            int_t j = i + 1;

            check(i, j);
        }
        if (maxpos == -1) {
            maxpos = n;
        }
        result[maxpos] = n;
        for (int_t i = 1; i <= n; i++) {
            if (i == maxpos)
                continue;
            cout << "? 2 " << i << " " << maxpos << " 1" << endl;
            ;
            int_t x;
            cin >> x;
            result[i] = x;
        }
        cout << "! ";
        for (int_t i = 1; i <= n; i++) {
            cout << result[i] << " ";
        }
        cout << endl;
    }
    return 0;
}