P4899 [IOI2018] werewolf 狼人

P4899 [IOI2018] werewolf 狼人

Meaning

给定一张连通图，每次询问从点 $S$ 走到点 $T$ 是否存在路径，使得前一部分路程不经过编号小于 $L$ 的点，后一部分路程不经过编号大于 $R$ 的点。

Sol

读懂题意后发现是 Kruskal 重构树的套路，考虑对于两部分路径分别构建重构树，那么显然我们按照边所连接的两点中最小值按照从大到小排序构建第一棵树，其次按照边所连接的两点中最大值按照从小到大构建第二棵树。每次询问倍增找到限制条件的临界点，此时我们得到了两颗子树，需要判断是否含有相同编号的结点。

显然想到把树上问题转化为 dfs 序变为序列问题，那么要求两个排列，询问两段区间是否含有相同编号结点。由于强制在线，我们考虑把两个排列建立映射关系，那么我们找到排列 2 中 dfs 序为 $i$ 的数对应在排列 1 中第 $i$ 个数的 dfs 序，据此建立主席树，那么每次查找一段区间 $[l_1, r_1]$ 中是否含有值域在 $[l_2, r_2]$ 中的点。其中 $l_1, r_1, l_2, r_2$ 为两个排列对应的端点位置。

Detail

1. 构建重构树时排序关键字选取一定正确；
2. 主席树动态开点时变量名不能紊乱冲突；
3. 排列映射关系推导一定正确。

Code

#include <iostream>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;

template <typename T>
inline T read() {
    T x = 0, f = 1; char c = getchar();
    while (!isdigit(c)) { if (c == '-') f = - f; c = getchar(); }
    while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
    return x * f;
}

#define lint long long int
#define ulint unsigned lint
#define readint read <int> ()
#define readlint read <lint> ()
const int inf = 1e9 + 1e7, MAXN = 8e5 + 1e1;
const lint INF = 1e18 + 1e9;

struct edge { int u, v; } c[MAXN];
struct Edge { int nxt, to; } ;
struct Node { int ls, rs, sz; } ;

int rt[MAXN], to[MAXN], n, m, q, nodecnt;

bool CmpMax(edge A, edge B) { return min(A.u, A.v) > min(B.u, B.v); }
bool CmpMin(edge A, edge B) { return max(A.u, A.v) < max(B.u, B.v); }

struct PW_SegmentTree {
    Node tree[MAXN << 5];

    #define ls(x) tree[x].ls
    #define rs(x) tree[x].rs
    #define sz(x) tree[x].sz

    void Insert(int l, int r, int p, int u, int &x) {
        x = ++ nodecnt, sz(x) = sz(u) + 1;
        if (l != r) {
            int mid = l + r >> 1;
            if (p <= mid) rs(x) = rs(u), Insert(l, mid, p, ls(u), ls(x));
            else ls(x) = ls(u), Insert(mid + 1, r, p, rs(u), rs(x));
        }
        return ;
    }

    int Query(int l, int r, int ql, int qr, int u, int x) {
        if (ql <= l && r <= qr) return sz(u) - sz(x);
        int mid = l + r >> 1, res = 0;
        if (ql <= mid) res += Query(l, mid, ql, qr, ls(u), ls(x));
        if (mid < qr) res += Query(mid + 1, r, ql, qr, rs(u), rs(x));
        return res;
    }

} pwst;

struct KruskalTree {
    int ffa[MAXN][20], head[MAXN], dfn[MAXN], fa[MAXN], sz[MAXN], f[MAXN], cnt, tot, dfncnt;
    Edge e[MAXN << 2];

    int Find(int x) { return (fa[x] == x ? x : fa[x] = Find(fa[x])); }

    void Addedge(int u, int v) { e[++ tot] = (Edge){head[u], v}, head[u] = tot; return ; }

    void Dfs(int u) {
        if (u <= n) dfn[u] = ++ dfncnt, sz[u] = 1;
        else dfn[u] = inf, sz[u] = 0;
        for (int i = 1; i <= 19; i ++) ffa[u][i] = ffa[ffa[u][i - 1]][i - 1];
        for (int i = head[u]; i; i = e[i].nxt) {
            int v = e[i].to;
            if (ffa[u][0] == v) continue ; ffa[v][0] = u;
            Dfs(v), dfn[u] = min(dfn[v], dfn[u]), sz[u] += sz[v];
        }
        return ;
    }

    void Build(bool type) {
        cnt = n;
        sort(c + 1, c + m + 1, (type ? CmpMax : CmpMin));
        for (int i = 1; i <= n; i ++) fa[i] = i;
        for (int i = 1; i <= m; i ++) {
            int u = c[i].u, v = c[i].v, fu = Find(u), fv = Find(v);
            if (fu != fv) {
                f[++ cnt] = (type ? min(u, v) : max(v, u)), fa[cnt] = fa[fu] = fa[fv] = cnt;
                Addedge(cnt, fu), Addedge(cnt, fv), Addedge(fu, cnt), Addedge(fv, cnt);
            }
        }
        Dfs(cnt);
        return ;
    }

    int Query(int u, int x, bool type) {
        if (type) for (int i = 19; i >= 0; i --) {
            if (ffa[u][i] && f[ffa[u][i]] >= x) u = ffa[u][i];
        }
        else for (int i = 19; i >= 0; i --) {
            if (ffa[u][i] && f[ffa[u][i]] <= x ) u = ffa[u][i];
        }
        return u;
    }

} kt1, kt2;

int main(void) {

    n = readint, m = readint, q = readint;
    for (int i = 1; i <= m; i ++) { int u = readint + 1, v = readint + 1; c[i] = (edge){u, v}; }
    kt1.Build(true), kt2.Build(false);
    for (int i = 1; i <= n; i ++) to[kt2.dfn[i]] = i;
    for (int i = 1; i <= n; i ++) pwst.Insert(1, n, kt1.dfn[to[i]], rt[i - 1], rt[i]);
    while (q --) {
        int s = readint + 1, t = readint + 1, l = readint + 1, r = readint + 1;
        int L = kt1.Query(s, l, true), R = kt2.Query(t, r, false);
        int ql1 = kt1.dfn[L], qr1 = kt1.dfn[L] + kt1.sz[L] - 1, ql2 = kt2.dfn[R], qr2 = kt2.dfn[R] + kt2.sz[R] - 1;
        printf("%d\n", (pwst.Query(1, n, ql1, qr1, rt[qr2], rt[ql2 - 1]) > 0));
    }

    return 0;
}