题意:有一长度为\(n\)的排列\(p\),有两种询问,第一种可以询问\(p\)的两个不同为位置\(i\)和\(j\)和一个数\(x\)并返回\(max(min(x,p_i),min(x+1,p_j))\),第二种返回\(min(max(x,p_i),max(x+1,p_j))\).要求你在\(\lfloor\frac{3*n}{2}\rfloor+30\)次询问内确定排列\(p\).

题解:我们可以先确定\(1\)的位置,然后不断去询问操作1,\(x\)取\(n-1\),也就变成\(max(min(1,p_i),min(n-1+1,p_j))\),即\(max(1,p_j)\),那么一次询问就可以确定一个值,那么就可以\(O(n)\)确定除了\(1\)的其他值,关键在于\(1\)怎么找,此时我们还剩下\(\frac{1}{2}*n\)可以用,其实可以用操作2\((1,2,x=1),(3,4,x=1),(5,6,x=1)....\)这样来问,那么假如\(i=1\),就直接返回,我们就能直接确定,如果\(j=1\),返回的值就为\(2\),此时我们在交换\(i\)和\(j\)再询问一次,这样就可以最多\(\frac{n}{2}+2\)次确定\(1\)的位置.

代码:

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
#define rep(a,b,c) for(int a=b;a<=c;++a)
#define per(a,b,c) for(int a=b;a>=c;--a)
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}
 
 
 
int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int _;
	cin>>_;
	while(_--){
		int n;
		cin>>n;
 
		int pos=n;  //n如果是奇数,j取不到n,所以如果a_n=1,我们就取不到这个1,所以要pos=n
		vector<int> ans(n+1);
		for(int i=1,j=2;j<=n;i+=2,j+=2){  
			cout<<"? 2 "<<i<<' '<<j<<' '<<1<<'\n';
			cout.flush();
			int x;
			cin>>x;
			if(x==1){
				pos=i;
				break;
			}
			else if(x==2){
				cout<<"? 2 "<<j<<' '<<i<<' '<<1<<'\n';
				cout.flush();
				cin>>x;
				if(x==1){
					pos=j;
					break;
				}
			}
		}
		ans[pos]=1;
		rep(i,1,n){
			if(i==pos) continue;
			cout<<"? 1 "<<pos<<' '<<i<<' '<<n-1<<'\n';
			cout.flush();
			int x;
			cin>>x;
			ans[i]=x;
		}
		//times=1/2*n+n+max(2)
		cout<<"! ";
		rep(i,1,n) cout<<ans[i]<<' ';
		cout<<'\n';
		cout.flush();
	}
	
 
 
 
    return 0;
}