LOJ6736. 「2020 集训队论文」最小连通块

LOJ6736. 「2020 集训队论文」最小连通块

考虑用 $n \log n$ 时间还原出一种拓扑序。将 $1$ 节点设为根节点，对于每个加入的节点 $x$ ，对于一个点 $p$ ，如果前缀集合不加入它则查询为 false ，加入为 true ，说明 $p$ 是 $x$ 儿子，将点 $x$ 插入到 $p$ 前。最后构造出拓扑序。

按照拓扑序从后向前枚举每一个点 $x$ ，维护一个当前根节点集合，同样地，如果多一个点 $p$ 从 false 转变为 true ，则说明 $(x, p)$ 有边。

二分查询。

查看代码

#include "C.hpp"
#include <vector>
using namespace std;
#define ep emplace_back
typedef vector <int> VI;
typedef pair <int, int> PII;
VI a, b;
vector <PII> work(int n)
{
    a.ep(1);
    for (int i = 2; i <= n; ++i)
    {
        int l = 1, r = i - 1, p = i;
        while (l <= r)
        {
            int mid = l + r >> 1;
            ask(VI(a.begin(), a.begin() + mid), i) ? (p = mid, r = mid - 1) : (l = mid + 1);
        }
        a.insert(a.begin() + p - 1, i);
    }
    vector <PII> res;
    b.ep(1);
    for (int i = n - 1; i; --i)
    {
        int x = a[i];
        while (ask(VI(b.begin(), b.end()), x))
        {
            int l = 1, r = b.size() - 1, p = 0;
            while (l <= r)
            {
                int mid = l + r >> 1;
                ask(VI(b.begin(), b.begin() + mid + 1), x) ? (p = mid, r = mid - 1) : (l = mid + 1);
            }
            res.ep(b[p], x), swap(b[p], b.back()), b.pop_back();
        }
        b.ep(x);
    }
    for (int i : b) if (i ^ 1) res.ep(i, 1);
    return res;
}