题解：P17767 「LDOI R2」排列 / Permutation

· · 题解

挺好的交互题。

首先可以发现，这个限制非常严格，具体的，实际上我们需要满足对于所有 i,j 都有 |a_i-a_j|=|b_i-b_j|。而对于这个限制，显然只有当所有的 b_i=a_i 或者所有的 b_i=n-a_i+1 时成立。

接下来的思路方向是考虑将 b_1 以及所有的 |b_i-b_1| 求出来。

假设我们知道了某个 |b_i-b_1|，不妨认为是 |b_2-b_1|，那么对于其他的 |b_i-b_1| 都可以通过询问 i 1 2 轻松得到。而对于 |b_2-b_1|，我们可以通过询问 3 1 2 和 1 3 2 和 3 2 1 解方程得到。

那么现在我们花费了大约 n 次询问得到所有的 |b_i-b_1|。

那么如何计算 b_1 呢？容易发现我们将所有的 |b_i-b_1| 求和实际上就是对所有的 |i-b_1| 求和。那么这样就可以二分了，不过根据最开始的分析可知 b_1 有两种取值，我们倾定二分得到的 b_1\le \frac{n}{2}，具体原因见下文。

接下来对于每个 b_i，记录 c_i=|b_i-b_1|，则他要么是 b_1+c_i 要么是 b_1-c_i，对于最大的 c_i，它对应的 b_i 显然是 n，因为 b_1\le \frac{n}{2}。进一步分析可以发现，当 b_1-c_i\le 0 时，b_i 显然只能是 b_i+c_i，于是我们现在只需要考虑 c_i<b_i 的情况。

我们现在已经有了 n 的位置，这是很好的，因为所有的数都比 n 小。具体的，假设 b_p=n，如果我们询问 i p j 那么得到的值便是 2n-b_i-b_j，这样一来我们只需要保证 c_i\ne c_j 便可以确定 b_i,b_j 的值了，于是每次两两分组即可。最后可能剩下一组 c_i=c_j，询问 p i j 即可。此时我们只用了大约 \frac{n}{4} 次询问。

我们惊人的发现 80000+20000=100000，于是就对了。

::::info[Code]

#include <bits/stdc++.h>
using namespace std;
int query(int i, int j, int k);
int a[1000005], b[1000005];
vector<int>g[1000005];

vector<int> solve(int n, int sid) {
    int x = query(3, 1, 2), y = query(1, 3, 2), z = query(3, 2, 1);
    //|a1-a2|
    //|a3-a1|+k=x,|a3-a1|+|a3-a2|=y,|a3-a2|+k=z
    int k = (x - y + z) / 2;
    //b[i]:|ai-a1|+k
    b[3] = x;
    b[2] = 2 * k;
    long long sum = 0;
    for (int i = 4; i <= n; i++)
        b[i] = query(i, 1, 2), sum += b[i] - k;
    sum += x;
    int l = 1, r = (n + 1) / 2, ans = 0;
    //\sum |ai-a1|=sum
    while (l <= r) {
        int mid = (l + r) / 2;
        long long z = 1LL * mid * (mid - 1) / 2 + 1LL * (n - mid + 1) * (n - mid) / 2;
        if (z <= sum)
            ans = mid, r = mid - 1;
        else
            l = mid + 1;
    }
    //求出a[1]
    a[1] = ans;
    //a[i]=a[1]+b[i]或a[1]-b[i]
    //因为a[1]<=(n+1)/2（超过了则变为n-a[1]+1），所以b[i]最大的点是n
    for (int i = 2; i <= n; i++)
        b[i] -= k;
    int p = 0;
    for (int i = 2; i <= n; i++)
        if (b[i] > b[p])
            p = i;
    a[p] = n;
    for (int i = 2; i <= n; i++)
        g[b[i]].push_back(i);
    int u = ans - 1;
    if (n % 2 == 1 && ans == (n + 1) / 2 && ans - 1 == b[p]) {
        a[g[b[p]][1]] = 1;
        u--;
    }
    for (int i = u + 1; i <= b[p]; i++)
        for (int x : g[i])
            if (!a[x])
                a[x] = ans + i;
    vector<int>as;
    for (int i = 1; i <= u; i++)
        as.push_back(i);
    int now = 0;
    while (now + 1 < (int)as.size()) {
        int x = as[now], y = as[now + 1];
        int p1 = g[x][0], p2 = g[y][0];
        int tmp = 2 * n - query(p1, p, p2);
        for (int i = -1; i <= 1; i++) {
            for (int j = -1; j <= 1; j++) {
                if (i * j == 0)
                    continue;
                if (ans + i * x + ans + j * y == tmp) {
                    a[p1] = ans + i * x, a[g[x][1]] = 2 * ans - a[p1];
                    a[p2] = ans + j * y, a[g[y][1]] = 2 * ans - a[p2];
                    break;
                }
            }
        }
        now += 2;
    }
    if (now < (int)as.size()) {
        int x = as[now];
        int p1 = g[x][0], p2 = g[x][1];
        int tmp = query(p, p1, p2);
        for (int i = -1; i <= 1; i++) {
            if (!i)
                continue;
            int z = ans + i * x;
            if (n - z + abs(2 * ans - 2 * z) == tmp) {
                a[p1] = z;
                a[p2] = 2 * ans - z;
                break;
            }
        }
    }
    vector<int>da;
    for (int i = 1; i <= n; i++)
        da.push_back(a[i]);
    return da;
}

::::