自动搬运

查看原文

来自洛谷，原作者为

	沉石鱼惊旋 已完成今日我对着铁质的凳子踢了五下然后把那堆钢栏杆在地上滚了一下然后把椅子夹在了篮筐上大学习

搬运于2025-08-24 23:11:32，当前版本为作者最后更新于2025-03-27 19:16:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

一棵 $n$ 个节点的有根树，以 $0$ 为根。每个点 $u$ 有一个 $p_u$。对于所有 $u$，$u$ 的父亲 $fa$ 总是满足 $p_{fa}\lt p_u$。

你可以给出 $u\neq v$ 的一对 $u,v$ 调用交互库 $\operatorname{compare}(u,v)$ 查询 $[p_u\lt p_v]$ 。

还原排列。

设 $P$ 表示这棵树所有可能的 $p$ 的个数，$Z=\lceil \log_2 P\rceil$，你调用了 $C$ 次交互库，令 $K=C/Z$。当 $Z=0$ 的时候，如果 $C\gt 0$，那么 $K=10^9$，否则 $K=0$。只有 $K\leq 1.4$ 时才能获得满分。

$2\leq N\leq 10^4$。

做法

设 $V_u$ 表示 $u$ 子树内排好序的序列。

初始 $V_u$ 为空，之后一直加入 $V_v(v\in \operatorname{son}(u))$。把 $V_u$ 和 $V_v$ 合并起来。全部合并完之后把 $u$ 插到 $V_u$ 开头。

考虑优化这个插入的部分。

一个想法是分块，设合并的序列是 $V_1,V_2$，长度 $L_1,L_2$ 且 $L_1\geq L_2$。块长设为 $B$。然后取出 $V_1$ 每个块第一个元素和 $V_2$ 归并排序。最后在块内二分出这个元素最后的位置。

这个做法需要 $\lceil L_1/B \rceil+L_2-1+L_2\times (\lceil\log_2(B-1)\rceil+1)$ 次操作。

考虑尽量把这个 $B$ 卡到 $2^k+1$。这样块内二分次数不变。但是归并次数可以变少。

直接这样做分够高了但是过不去。大概有八十多分。

如果 $V_2$ 元素很少 $V_1$ 元素很多我们还有 $L_2\times \lceil\log_2(L_1+1)\rceil$ 次操作的做法。就是直接把整个序列看成一块直接二分（不用取出第一个元素）。

分块策略枚举块长算一个最优解出来，和第二种做法次数比较一下，选择次数更小的策略。这里次数写出来的式子要卡精细一点。

代码

https://qoj.ac/submission/951035

#include <bits/stdc++.h>
#include "evolution2.h"
using namespace std;
vector<int> recover(int N, vector<int> U, vector<int> V)
{
    int n = N;
    vector<int> p;
    vector<vector<int>> a(n);
    vector<vector<int>> vec(n);
    for (int i = 0; i < n - 1; i++)
    {
        auto [u, v] = tie(U[i], V[i]);
        a[u].emplace_back(v);
        a[v].emplace_back(u);
    }
    auto merge = [&](vector<int> &a, vector<int> &b)
    {
        if (a.empty())
            return b;
        if (b.empty())
            return a;
        if (a.size() < b.size())
            swap(a, b);
        vector<int> t;
        int cnt = a.size() + b.size() - 1, l = 0;
        auto upd = [&](int len)
        {
            int times = (a.size() + len) / (len + 1) + b.size() - 1 + b.size() * (__builtin_ctz(len) + 1);
            if (times < cnt)
                cnt = times, l = len;
        };
        int len = 1;
        upd(len);
        while (len + 1 < a.size())
        {
            len <<= 1;
            upd(len);
        }
        len = l + 1;
        l = 1;
        while (l < a.size() + 1)
            l <<= 1;
        vector<int> v;
        int i = 0, j = 0;
        vector<int> pos(b.size());
        if (b.size() * __builtin_ctz(l) < cnt)
        {
            for (int p = 0; p < b.size(); p++)
            {
                pos[p] = !p ? -1 : pos[p - 1];
                int l = !p ? 0 : pos[p - 1] + 1, r = a.size() - 1;
                while (l <= r)
                {
                    int mid = l + r >> 1;
                    if (compare(a[mid], b[p]))
                        l = (pos[p] = mid) + 1;
                    else
                        r = mid - 1;
                }
                if (pos[p] == -1)
                    v.emplace_back(b[p]);
            }
        }
        else
        {
            for (int i = 0; i < a.size(); i += len)
                t.emplace_back(a[i]);
            int c = 0;
            while (i < t.size() || j < b.size())
            {
                if (i == t.size())
                    v.emplace_back(-(++j));
                else if (j == b.size())
                    v.emplace_back((i++) * len);
                else if (compare(t[i], b[j]))
                    v.emplace_back((i++) * len);
                else
                    v.emplace_back(-(++j));
            }
            int lst = -1;
            t = v;
            v.clear();
            for (int p : t)
            {
                if (p >= 0)
                    lst = p;
                else
                {
                    p = -p - 1;
                    if (~lst)
                    {
                        pos[p] = lst;
                        int l = lst + 1, r = min((int)a.size() - 1, lst + len - 1);
                        while (l <= r)
                        {
                            int mid = l + r >> 1;
                            c++;
                            if (compare(a[mid], b[p]))
                                l = (pos[p] = mid) + 1;
                            else
                                r = mid - 1;
                        }
                    }
                    else
                    {
                        pos[p] = -1;
                        v.emplace_back(b[p]);
                    }
                }
            }
        }
        i = 0, j = 0;
        while (pos[j] == -1)
            j++;
        while (i < a.size() || j < b.size())
        {
            if (i == a.size())
                v.emplace_back(b[j++]);
            else if (j == b.size())
                v.emplace_back(a[i++]);
            else if (i <= pos[j])
                v.emplace_back(a[i++]);
            else
                v.emplace_back(b[j++]);
        }
        return v;
    };
    auto dfs = [&](auto self, int u, int fa) -> void
    {
        for (int v : a[u])
        {
            if (v == fa)
                continue;
            self(self, v, u);
            vec[u] = merge(vec[u], vec[v]);
        }
        vec[u].insert(vec[u].begin(), u);
    };
    dfs(dfs, 0, -1);
    p = vec[0];
    vector<int> q(n);
    for (int i = 0; i < n; i++)
        q[p[i]] = i;
    return q;
}