IOI 2018 Day1 T3 Werewolf Solution

题目大意

给定无向联通图，$q$ 次询问 $s,t,l,r$，求是否存在一个点 $p$，使得 $s\rightarrow p $ 的路径上所经过点的编号 $\ge l$，且 $p \rightarrow t$ 的路径上所经过点的编号 $\le r$。

$n\le 2\times 10^5,m\le 4\times 10^5$

Solution

容易发现，前半部分的约束相当于所经过点编号的最小值 $\ge l$，后半部分同理，和瓶颈路十分类似。

瓶颈路：求一条 $s\rightarrow t $ 的路径，使得其中经过的边权最小值最大或最大值最小。

Kruskal 重构树

当我们用 Kruskal 求图上的最小生成树时，我们可以在合并两个森林时新建一个点，并令这个点的点权为当前边的边权，将两个森林合并到这个点上，这样所构造出来的一棵树称为 Kruskal 重构树。

根据最小生成树的性质，在原图上任取两个点 $u,v$，这两个点的最小瓶颈路上的最大边权即为重构树上 $\text{LCA}(u,v)$ 上的点权。

就本题而言，借助 Kruskal 重构树的思想，构造以点编号为关键字的重构树，满足点的编号随树深度的递增而递增或递减。

例如，对于左半部分的重构树，可以 $1\sim n$ 遍历每一个点 $u$，如果相连的点的编号 $v$ 小于 $u$ 则将 $u$ 的祖先置为 $v$。那么在这棵重构树上，$s$ 不断向上倍增找到一个编号最小的且编号 $\ge l$ 的祖先 $fa$，从而 $s$ 可以在 $l$ 的限制下到达 $fa$ 子树的所有点。

至此，问题转化为两个子树内的点是否有交集。

有一种离线做法，即将求交集看作二维数点，用树状数组维护即可做到 $O(n\log n)$。现在介绍一种在线做法。

主席树

主席树通过记录历史版本可以容易地维护区间中的序列信息，具体详见 OI wiki 中的介绍：可持久化线段树 OI-Wiki。

由于子树内的 dfs 序是连续的，可以通过在主席树中插入两个点的唯一映射 $(i,dfn2[rnk1[i])$，查询时直接判断区间内点的数量是否大于 $0$ 即可。

const int MAXN = 200000 + 5;
int n, m, Q, head[MAXN], nxt[MAXN << 2], ver[MAXN << 2], rt[MAXN << 6];
void add(int u, int v) {
    nxt[++head[0]] = head[u];
    ver[head[u] = head[0]] = v;
}
struct Edge {
    int f[MAXN], fa[MAXN][21], dfn[MAXN], sz[MAXN], rnk[MAXN];
    bool mark;
    std::vector<int> e[MAXN];
    int find(int x) {return x == f[x] ? x : f[x] = find(f[x]);}
    void build() {
        for (int i = 1; i <= n; i++) f[i] = i;
        for (int i = 1; i <= n && mark; i++)
            for (int j = head[i]; j; j = nxt[j]) {
                if (ver[j] > i) continue;
                int u = find(i), v = find(ver[j]);
                if (u == v) continue;
                f[v] = u;
                e[u].push_back(v);
            }
        for (int i = n; i && !mark; i--)
            for (int j = head[i]; j; j = nxt[j]) {
                if (ver[j] < i) continue; 
                int u = find(i), v = find(ver[j]);
                if (u == v) continue;
                f[v] = u;
                e[u].push_back(v);
            }
    }
    void dfs(int u, int _fa) {
        rnk[dfn[u] = ++dfn[0]] = u;
        sz[u] = 1;
        fa[u][0] = _fa;
        for (int i = 1; i <= 20; i++)
            fa[u][i] = fa[fa[u][i - 1]][i - 1];
        for (auto v : e[u]) {
            if (_fa == v) continue;
            dfs(v, u);
            sz[u] += sz[v];
        }
    }
    int calc(int x, int k) {
        for (int i = 20; ~i && mark; i--)
            if (fa[x][i] && fa[x][i] <= k) x = fa[x][i];
        for (int i = 20; ~i && !mark; i--)
            if (fa[x][i] && fa[x][i] >= k) x = fa[x][i];
        return x;
    }
}T1, T2;
struct Persistent_Segment_Tree {
    int val[MAXN << 6], tol, ls[MAXN << 6], rs[MAXN << 6];
#define mid ((l + r) >> 1)
    void insert(int &x, int l, int r, int p, int &pre) {
        x = ++tol;
        val[x] = val[pre] + 1;
        if (l == r) return;
        if (p <= mid) rs[x] = rs[pre], insert(ls[x], l, mid, p, ls[pre]);
        else ls[x] = ls[pre], insert(rs[x], mid + 1, r, p, rs[pre]);
    }
    int query(int L, int R, int l, int r, int ll, int rr) {
        if (r < ll || l > rr) return 0;
        if (ll <= l && r <= rr) return val[R] - val[L];
        return query(ls[L], ls[R], l, mid, ll, rr) + query(rs[L], rs[R], mid + 1, r, ll, rr);
    }
} st;
int main() {
    io >> n >> m >> Q;
    for (int i = 1, u, v; i <= m; i++) {
        io >> u >> v;
        u++; v++;
        add(u, v); add(v, u);
    }
    T1.mark = false; T2.mark = true;
    T1.build(); T2.build();
    T1.dfs(1, 0); T2.dfs(n, 0);
    for (int i = 1; i <= n; i++)
        st.insert(rt[i], 1, n, T2.dfn[T1.rnk[i]], rt[i - 1]);
    for (int s, t, l, r; Q--;) {
        io >> s >> t >> l >> r;
        s++; t++; l++; r++;
        int x = T1.calc(s, l), y = T2.calc(t, r);
        io << (st.query(rt[T1.dfn[x] - 1], rt[T1.dfn[x] + T1.sz[x] - 1], 1, n, T2.dfn[y], T2.dfn[y] + T2.sz[y] - 1) > 0) << '\n';
    }
    return 0;
}