题解：P5473 [NOI2019] I 君的探险

· · 题解

复读一下学长的题解。

考虑把题目弱化一下，假设图是一棵树，并且每个点的父亲编号都小于它。可以二分它的父亲所在区间 [l,r]，把整个区间都翻转一边，如果它的颜色变了，说明它的父亲在 [l,r] 这个区间里。

但是这样做显然操作次数过多，因为只给了你单点翻转。

考虑整体二分，记父亲在 [l,r] 内的点的集合为 S，在 [l,mid] 的中的为 LS，在 (mid,r] 中的为 RS，翻转 [l,mid]，如果 (mid,r] 中的点被翻转了，那么把它加入 LS，如果 S 中的点被翻转了，加入 LS，否则加入 RS。可以发现这样做的操作次数是够用的。

你发现 check 函数还没用过。

考虑怎么推广到一般图上，你发现直接放上去就是对的。只是可能有多个父亲，所以可能会出现偶数个父亲在区间里，导致你会认为它的父亲不在这个区间里。

考虑随机化，每次打乱你考虑的点的顺序，这样就可能被洗成奇数条边，然后 report 一条边后就把它删掉，就是每次翻转的时候把这个点连接的已经 report 的边连接的另一个点翻转了，然后如果询问结果和数组相同说明没被翻转过，然后一整体二分后把所有点 check 一遍，如果记录完了，就把这个点踢出排列。重复上述操作直至记录完所有边。

考虑为啥是对的。一个度数为 x 的点有 \dfrac{x/2}{x} 的概率父亲为奇数。当 x=3 时值最小。所以最坏会使排列大小减小 \dfrac{x}{3}。有式子 T(m)=T(m-m/3) + \mathcal{O}(m \log m)，所以 T(m) = \mathcal{O}(m \log m)。

注意 1~5 的测试点用上述做法不能通过，只能补个暴力拼上去。原因给个图。

#include <bits/stdc++.h>
using namespace std;
void modify(int x);
int query(int x);
void report(int x, int y);
int check(int x);
mt19937 rnd(time(0));
const int N = 2e5 + 5;
vector<int> g[N];
int cnt, s[N];
inline void solve(int l, int r, vector<int> p, const vector<int>& V) {
    if (l == r) {
        for (auto i : p) {
            g[i].push_back(V[l]), g[V[l]].push_back(i);
            report(i, V[l]);
            ++cnt;
        }
        return ;
    }
    int mid = l + r >> 1; vector<int> pl, pr;
    for (int i = l; i <= mid; ++i) {
        modify(V[i]);
        s[V[i]] ^= 1;
        for (auto v : g[V[i]]) s[v] ^= 1;
    }
    for (int i = mid + 1; i <= r; ++i) if (query(V[i]) ^ s[V[i]]) pl.push_back(V[i]);
    for (auto i : p) {
        if (query(i) ^ s[i]) pl.push_back(i); 
        else pr.push_back(i);
    }
    for (int i = l; i <= mid; ++i) {
        modify(V[i]);
        s[V[i]] ^= 1;
        for (auto v : g[V[i]]) s[v] ^= 1;
    }
    solve(l, mid, pl, V), solve(mid + 1, r, pr, V);
}
void explore1(int N, int M) {
    for (int i = 0; i < N - 1; ++i) {
        modify(i);
        s[i] ^= 1;
        for (auto v : g[i]) s[v] ^= 1;
        for (int j = i + 1; j < N; ++j) {
            if (query(j) ^ s[j]) {
                s[j] ^= 1;
                report(i, j);
                g[i].push_back(j), g[j].push_back(i);
            }
        }
    }
}
void explore2(int N, int M) {
    vector<int> V;
    for (int i = 0; i < N; ++i) V.push_back(i);
    while (1) {
        solve(0, V.size() - 1, {}, V);
        if (cnt == M) break;
        vector<int> t;
        for (auto i : V) if (!check(i)) t.push_back(i);
        V = t; shuffle(V.begin(), V.end(), rnd);
    }
}
void explore(int N, int M) {
    if (N <= 500) explore1(N, M);
    else explore2(N, M);
}