P8375 [APIO2022] 游戏

psoet · 2022-06-09 15:55:02 · 题解

O((n + m)k)

一个点能够到达的链上部分是一个后缀，能到达一个点的链上部分是一个前缀，分别记作 $suf_u$ 和 $pre_u$ ，如果没法到链/没法从链到达则分别记为 $k$ 和 $-1$ 。那么对于一个不是特殊点的 $u$ ，存在一个过 $u$ 和特殊点的环当且仅当 $pre_u \geq suf_u$ 。注意特别处理链上“回边”的情况。我们可以在加边的时候同时维护 $pre$ 和 $suf$ ，暴力搜，每次只更新需要更新的点。这样复杂度是 $O((n+m)k)$ 。 #### $O((n + m) \log k)

（下面内容主要参考自 dengyaotriangle 在LOJ上的提交记录）

维护 pre 和 suf 的全部变化显然是做不下去的。

但是注意：对 pre 和 suf 的修改并不需要一步到位。我们只需把它修改到某个是否有环一目了然的状态即可。

我们对 [-1,k] 建一棵线段树。在还没找到环的时候， [pre_u,suf_u] 构成一些区间。

一开始，所有的特殊点区间都对应叶子，所有的非特殊点区间都对应根节点。

我们声称：每个区间都只需调整到线段树的某个节点。

假设当前连了一条边 u \rightarrow v 。首先特判掉 u 和 v 均是特殊点的情况。

线段树的两个区间只有三种位置关系：相离、包含和重合（我们单独考虑重合）。

下面的推导中，我们只用承认两个基本事实：

只要可以判断是否有环，我们就不用进行下一步的调整。
如果 u \rightarrow v 没有在 u 和 v 的区间上带来改变，我们可以直接返回。

Case 1 u 和 v 的区间相离

分为两种情况：

假如 u 的区间在 v 的区间左边，一定不会有环出现，可以直接返回。

否则 u 的区间在 v 的区间右边，我们找到了一个环。

Case 2 u 和 v 的区间重合

这种情况不会带来环，我们可以直接返回。

当然，这里假设了 u 和 v 的当前区间不是叶子，否则在上一层我们就返回了。

Case 3 u 和 v 的区间相互包含

如果 v 的区间在 u 的左儿子内：

此时 u 的区间会被改成图中的样子，但我们只需把 u 变成其节点的左儿子，然后递归下去。

如果 u 的区间在 v 的右儿子内：

此时 v 的区间会被改成图中的样子，但我们只需把 v 变成其节点的右儿子，然后递归下去。

注意可能产生长度为 1 的区间，需要直接返回。

如果不进行这两步调整，我们就无法在这一步以及以后的过程中判断是否有环，所以它们是必要的。

其它两种情况，可以证明都不会产生环。比如，

这种情况下一定不会产生环，只需考虑和 mid_u 、mid_u + 1 的连通情况即可。

于是复杂度 O((n+m) \log k) 。

代码：

#include <bits/stdc++.h>

#include "game.h"

#define For(i, a, b) for (int i = a, i##end = b; i <= i##end; ++i)
#define rFor(i, b, a) for (int i = b, i##end = a; i >= i##end; --i)

const int kN = 3e5 + 5;

int n, k, lb[kN], rb[kN];
std::vector<int> G[kN][2];

void init(int _n, int _k) {
    n = _n, k = _k;
    std::fill(lb, lb + n, -1);
    std::fill(rb, rb + n, k);
    For(i, 0, k - 1) {
        lb[i] = rb[i] = i;
    }
}

bool add(int, int);

bool add(int u) {
    for (int v : G[u][0]) if (add(u, v)) return true;
    for (int v : G[u][1]) if (add(v, u)) return true;
    return false;
}

bool add(int u, int v) {
    if (u < k && v < k) return u >= v;
    if (rb[u] < lb[v]) return false;
    if (lb[u] > rb[v]) return true;
    if (lb[u] == lb[v] && rb[u] == rb[v]) return false;
    int midu = (lb[u] + rb[u]) >> 1, midv = (lb[v] + rb[v]) >> 1;
    if (lb[v] >= lb[u] && rb[v] <= midu) {
        rb[u] = midu;
        return lb[u] == rb[u] || add(u);
    }
    if (rb[u] <= rb[v] && lb[u] > midv) {
        lb[v] = midv + 1;
        return lb[v] == rb[v] || add(v);
    }
    return false;
}

int add_teleporter(int u, int v) {
    G[u][0].push_back(v), G[v][1].push_back(u);
    return add(u, v);
}

根据WeLikeStudying的题解，应该存在一种跟二进制分组有关的做法。

这是比较自然的：这个问题很容易用离线分治解决，而二进制分组的名头就在于它可以在线地解决一类 cdq 分治能够解决的问题。

但以前见过的例子都是可以分体贡献的，这个好像不太一样。而且我没看懂他写的东西/kk。并不知道二进制分组怎么扩展到更一般的问题。