洛谷P6960 [NEERC2017] Interactive Sort 题解

题目链接：P6960 [NEERC2017] Interactive Sort

题意：

这是一道 IO 交互题。

有一个长度为 \(n~(n\le 10^4)\) 的排列，将排列按奇偶分为两个序列

记所有偶数组成的序列为 \(a\) ，所有奇数组成的序列为 \(b\) ，初始未知。

你可以进行不超过 \(3\times 10^5\) 次询问 ? i j，每次交互库会返回一个 < 或 > 表示 \(a_i\) 和 \(b_j\) 的大小关系。

最后你需要求出 \(a,b\) 并输出，格式为 ! a b。保证数据随机。

首先最简单的方案就是暴力询问每个偶数和每个奇数。

注意到每次询问偶数 \(a_i\) ，都会将奇数序列分为两个集合，分别是大于 \(a_i\) 的和小于 \(a_i\) 的。（\(a_i=n\) 除外）

那么当我们每询问出一个 \(a_i\) ，\(b\) 中的某个集合就会分成两个。

如果我们取集合内的任意一个元素作为集合的权值，那么这些集合的权值显然是单调的

于是对于每个 \(a_i\) ，我们二分出它可能位于哪两个块，然后暴力比较块里面的元素

这样就可以将一个已知集合划分成两个，同时也知道 \(a_i\) 的值。

我们考虑按随机的顺序问 \(a_i\) （不过这题保证了随机所以顺序问也可以）

问完 \(i\) 个 \(a\) 后每个块的期望大小约为 \(\frac{n}{2i}\) 。暴力问两个块，最坏情况下期望问 \(\frac{n}{i}\) 次。

再加上二分的次数，故期望询问次数为 \(\sum_{i=1}^n \log_2i\) ，当 \(n=10^4\) 次期望询问 \(1.45 \times 10^5\) 次。

时间复杂度 \(\mathcal{O}(n \ln n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(1e4 + 55))
#define pb push_back

struct node { int l, r; vector<int> v; };
vector<node> vec; mt19937 rd(time(0)); int n, a[N], b[N], p[N];
bool ask(int x, int y)
{
    static char c;
    cout << "? " << x << ' ' << y << endl;
    cin >> c; return c == '>';
}
void answer(vector<int> &v1, vector<int> &v2)
{
    rep(i, 1, n / 2) v1.pb(a[i]);
    rep(i, 1, (n + 1) / 2) v2.pb(b[i]);
    cout << "! "; for(auto i : v1) cout << i << ' ';
    for(auto i : v2) cout << i << ' '; cout.flush();
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n; node _ = {1, (n + 1) / 2 * 2 - 1};
    rep(i, 1, (n + 1) / 2) { _.v.pb(i); } vec.pb(_);
    rep(i, 1, n / 2) { p[i] = i; } shuffle(p + 1, p + 1 + n / 2, rd);
    rep(i, 1, n / 2)
    {
        int l = 0, r = vec.size() - 1;
        while(r - l + 1 > 2)
        {
            int mid = (l + r) >> 1;
            if(ask(p[i], vec[mid].v[0])) l = mid; else r = mid;
        }
        bool ck = true;
        rep(j, l, r)
        {
            vector<int> v1, v2;
            for(int x : vec[j].v) if(ask(p[i], x)) v1.pb(x); else v2.pb(x);
            if(v1.empty() || v2.empty()) continue;
            ck = false; if(j) { a[p[i]] = vec[j - 1].r + 1; }
            a[p[i]] += v1.size() * 2;
            node t = {a[p[i]] + 1, vec[j].r};
            vec[j].r = a[p[i]] - 1; vec[j].v = v1;
            t.v = v2; vec.insert(vec.begin() + j + 1, t); break;
        }
        if(ck) { a[p[i]] = n; }
    }
    for(auto i : vec) b[i.v[0]] = i.l;
    vector<int> v1, v2; answer(v1, v2);
    return 0;
}