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

xzys · 2026-10-24 19:37:28 · 题解

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

思路

注意到等价，因此我们不需要还原出数值，可以把 a_1 作为参考，先求出所有点到 a_1 的距离差，再确定每个点在 a_1 的左侧还是右侧，最后生成出相对顺序一致的等价排列。

首先我们需要知道每一个点到 a_1 的绝对距离。通过查询 (2, 1, 3)、(1, 2, 3) 和 (1, 3, 2) 可以直接算出 |a_1 - a_2|，令这个为 \mathrm{dqr}。

对于剩下的点 i \ge 4，通过查询 (2, 1, i) 减去 \mathrm{dqr} 就可以算出所有点到 a_1 的距离 \mathrm{dq}_i = |a_1 - a_i|。

在掌握了所有点到 a_1 的距离绝对值后，下一步需要确定每个元素在 a_1 的左边还是右边。

先找出距离 a_1 最远的点 q，记它的距离为 d = \mathrm{dq}_q。由于 a_1 在整个排列的值域 [1, n] 中，它左侧有 a_1 - 1 个元素，右侧有 n - a_1 个元素。既然 q 离 a_1 最远，说明 a_1 必然偏向一侧，另一侧的元素个数恰好就是 d，从而我们可以推算出另一侧的大小 s = n - 1 - d。

之后对于那些距离大于 s 的点，由于空间限制它们必然只能落在更大的一侧，方向只能为负号。而对于距离较近的点，可以通过 p1 和 p2 记录相同距离在两侧的候选点，然后将它们两两配对，借助查询 (r, q, t) 询问它们与最远点 q 的组合距离，解出各自的正负符号。如果配对后有剩下的，可以通过与 1 号点的查询来判定。

最后，当每个点的距离 \mathrm{dq}_i 和方向 \mathrm{sgn}_i 都确定之后，就可以直接利用 b_i = d + \mathrm{sgn}_i \times \mathrm{dq}_i + 1 生成出最终的等价排列 b。

代码

::::success[代码]

#include <bits/stdc++.h>
using namespace std;

int query(int i, int j, int k);

vector<int> tmp, res, rep;
int q, f, s, d, dqr, md;
int dq[100005], b[100005];
int p1[100005], p2[100005], sgn[100005];

bool cmp(int a, int b) { return dq[a] < dq[b]; }

vector<int> solve(int n, int sid)
{
    res.clear();
    rep.clear();
    if (n <= 2)
    {
        res.push_back(1);
        if (n == 2)
            res.push_back(2);
        return res;
    }
    int tmp = query(2, 1, 3);
    dqr = (query(1, 2, 3) + tmp - query(1, 3, 2)) / 2;
    dq[1] = 0;
    dq[2] = dqr;
    q = 1;
    dq[3] = tmp - dqr;
    if (dq[3] > dq[q])
        q = 3;
    for (int i = 4; i <= n; i++)
    {
        dq[i] = query(2, 1, i) - dqr;
        if (dq[i] > dq[q])
            q = i;
    }
    if (dq[2] > dq[q])
        q = 2;
    d = dq[q], md = s = n - 1 - d;
    if (d == s)
        md = s - 1;
    for (int i = 1; i <= n; i++)
    {
        int j = dq[i];
        if (j >= 1 && j <= s)
        {
            if (p1[j] == 0)
                p1[j] = i;
            else
                p2[j] = i;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        if (dq[i] > s)
            sgn[i] = -1;
    }
    if (d == s)
    {
        sgn[q] = -1;
        for (int i = 1; i <= n; i++)
        {
            if (dq[i] == d && i != q)
            {
                sgn[i] = 1;
                break;
            }
        }
    }
    for (int j = 1; j <= md; j++)
    {
        if (p1[j])
            rep.push_back(p1[j]);
    }
    for (int i = 0; i + 1 < (int)rep.size(); i += 2)
    {
        int r = rep[i];
        int t = rep[i + 1];
        int val = query(r, q, t) - 2 * d;
        int dr = dq[r], dt = dq[t];
        for (int a = -1; a <= 1; a += 2)
        {
            for (int b = -1; b <= 1; b += 2)
            {
                if (a * dr + b * dt == val)
                {
                    sgn[r] = a;
                    sgn[t] = b;
                }
            }
        }
    }

    if (rep.size() % 2 == 1)
    {
        int r = rep.back();
        int val = query(r, q, 1) - 2 * d;
        if (val == dq[r])
            sgn[r] = 1;
        else
            sgn[r] = -1;
    }

    for (int j = 1; j <= md; j++)
    {
        int u = p1[j], v = p2[j];
        if (u && v)
            sgn[v] = -sgn[u];
    }

    for (int i = 1; i <= n; i++)
        b[i] = d + sgn[i] * dq[i] + 1;
    for (int i = 1; i <= n; i++)
        res.push_back(b[i]);
    return res;
}

::::