CF1918E

下午 WC 的课全是黑题不太想听于是 vp 了一场 div.2。然而 vp 的时候 [censored] 在医院所以大部分时间在和 [censored] 聊天（好像如果我去听课大部分时间也会在和 [censored] 聊天）。赛时有一点小 bug 没调完。

其实这就是个简单 *2200。

首先一个 O(n^2) 次询问的解很显然：对每个位置 i 不断查询直到返回 =，然后就可以通过大小关系直接给这 n 个数排序从而得到答案。

既然排序可以得到答案，我们考虑那些 O(n\log n) 的排序，比如借鉴快速排序的思路。

快速排序的过程中，我们需要对值域分治。要在控制 x 的值不变的情况下查询若干个位置的答案，从而把这些位置分成“>x”和“<x”两组（=x 可以直接得到答案），递归下去就可以得到答案。这看似不好办到，因为我们没法直接控制 x 的值。

不过其实这个问题很容易就能解决，我们只要找到 1 和 n 在哪里，就能随意控制 x 的值了。查询一次 1 可以让 x 减小 1，n 同理。

具体来讲，我们只要扫一遍 1\sim n ，对于每个位置，如果询问返回 < 就继续查直到不是 < 为止，否则直接不管。显然这样最多查询 O(n) 次（因为 x 最多增大 n 次），并且在 a_i=1 的地方一定可以取到 x=1。我们只要看 x 在哪里取到最小值即可。找 a_i=n 同理。

找 1 和 n 需要 O(n) 次询问。

快速排序部分，询问次数是 T(n)=2T(\dfrac{n}{2})+O(n)=O(n\log n)

在对一个值域区间的询问开始前，我们需要把 x 的值调整为这个区间的分割点 mid，这需要 |x-mid| 次询问。直接先序遍历就可以让这部分的总询问次数为 O(n\log n)。

常数是足够小的。

讲的可能不是很清楚，但是代码很清楚，详见代码。

#include<bits/stdc++.h>
using namespace std;
int p1,pn;
int ans[2005];
int query(int x){
    cout<<"? "<<x<<endl;
    cout.flush();
    string s;
    cin>>s;
    if(s[0]=='=')return 0;
    if(s[0]=='<')return -1;
    if(s[0]=='>')return 1;
    return 0114507537;
}
int cur;
void solve(int l,int r,vector<int>&v){
    // v 是值在 [l,r] 中的下标集合 
    if(l>r)return;
    if(l==r){
        ans[v[0]]=l;
        return;
    }
    int mid=(l+r)/2;
    while(cur>mid){
        query(p1);
        cur--;
    }
    while(cur<mid){
        query(pn);
        cur++;
    }
    vector<int>vl,vr;
    vl.clear();
    vr.clear();
    // 分成 [l,mid-1] 和 [mid+1,r] 
    for(int x:v){
        int tmp=query(x);
        if(tmp==0)ans[x]=mid;
        if(tmp==-1){
            vl.push_back(x);
            query(pn);
        }
        if(tmp==1){
            vr.push_back(x);
            query(p1);
        }
    }
    solve(l,mid-1,vl);
    solve(mid+1,r,vr);
} 
int main(){
    int T;
    cin>>T;
    while(T--){
        int n;
        cin>>n;
        //find 1&n
        p1=pn=1;
        int md=0x3f3f3f3f,d=0;
        for(int i=1;i<=n;i++){
            int tmp=query(i);
            d+=tmp;
            while(tmp==-1){
                tmp=query(i);
                d+=tmp;
            }
            if(d<md)p1=i,md=d;
        }
        md=-0x3f3f3f3f,d=0;
        for(int i=1;i<=n;i++){
            int tmp=query(i);
            d+=tmp;
            while(tmp==1){
                tmp=query(i);
                d+=tmp;
            }
            if(d>md)pn=i,md=d;
        }
        ans[p1]=1,ans[pn]=n;

        vector<int>tmp;
        tmp.clear();
        for(int i=1;i<=n;i++)if(i!=p1 && i!=pn)tmp.push_back(i);
        int val=query(pn);
        while(val==1)val=query(pn);
        cur=n;
        solve(2,n-1,tmp);
        cout<<"! ";
        for(int i=1;i<=n;i++)cout<<ans[i]<<' ';
        cout<<endl;
        cout.flush();
    }
    return 0;
    // quod erat demonstrandum
}