[IOI2018] werewolf 狼人 kruskal重构树，主席树

时间：2023-03-09 19:08:19
[IOI2018] werewolf 狼人 kruskal重构树，主席树

[IOI2018] werewolf 狼人

LG传送门

kruskal重构树好题。

日常安利博客文章

这题需要搞两棵重构树出来，这两棵重构树和我们平时见过的重构树有点不同（据说叫做点权重构树？），根据经过我们简化的建树方法，这两棵树不再是二叉树，但是仍具有kruskal重构树的优秀性质，建议结合后面的描述理解。

看这题需要首先我们从\(S\)走到\(T\)转化为分别从\(S\)和\(T\)出发寻找能共同到达的点，需要快速求出从某个点出发经过点权不大（小）于\(r\)（\(l\)）的点，考虑kruskal重构树。令每条边的的边权为所连接两点的较大（小）值，造两棵重构树，这样就可以像平时一样直接倍增做了，但是我们发现边权的信息实际上就是点权的信息，于是我们在建新树时就不另建新点了，这就是所谓的“点权重构树”。建出树处理倍增之后，我们的问题就变成了查询两棵树上两棵子树是否有交，用dfs序表达就是一个简单的二维数点的问题，直接主席树。

#include <cstdio>

#include <cctype>

#include <vector>

#define R register

#define I inline

#define B 1000000

using namespace std;

const int N = 200003;

char buf[B], *p1, *p2;

I char gc() { return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, B, stdin), p1==p2) ? EOF : *p1++; }

I int rd() {

    R int f = 0;

    R char c = gc();

    while (c < 48 || c > 57) c = gc();

    while (c > 47 && c < 58) f = f * 10 + (c ^ 48), c = gc();

    return f;

}

int s[N], rt[N], val[N], T;

vector <int> g[N];

struct edge { int g, s; };

struct segtree { int p, q, s; }e[N << 5];

struct kruskal {

    int h[N], f[N], fa[N][20], dfn[N], low[N], E, tim;

    edge e[N];

    I void add(int x, int y) { e[++E] = (edge){y, h[x]}, h[x] = E; }

    I int find(int x) {

        R int r = x, y;

        while (f[r] ^ r)

            r = f[r];

        while (x ^ r)

            y = f[x], f[x] = r, x = y;

        return r;

    }

    void dfs(int x) {

        dfn[x] = ++tim;

        R int i;

        for (i = 1; i < 20; ++i)

            fa[x][i] = fa[fa[x][i - 1]][i - 1];

        for (i = h[x]; i; i = e[i].s)

            dfs(e[i].g);

        low[x] = tim;

    }

}X, Y;

int modify(int k, int l, int r, int x) {

    R int t = ++T;

    e[t].p = e[k].p, e[t].q = e[k].q, e[t].s = e[k].s + 1;

    if (l == r)

        return t;

    R int m = l + r >> 1;

    if (x <= m)

        e[t].p = modify(e[k].p, l, m, x);

    else

        e[t].q = modify(e[k].q, m + 1, r, x);

    return t;

}

int query(int k, int t, int l, int r, int x, int y) {

    if (x <= l && r <= y)

        return e[t].s - e[k].s;

    R int m = l + r >> 1, o = 0;

    if (x <= m)

        o += query(e[k].p, e[t].p, l, m, x, y);

    if (m < y)

        o += query(e[k].q, e[t].q, m + 1, r, x, y);

    return o;

}

int main() {

    R int n = rd(), m = rd(), Q = rd(), i, x, y, l, r;

    for (i = 1; i <= m; ++i)

        x = rd() + 1, y = rd() + 1, g[x].push_back(y), g[y].push_back(x);

    for (i = 1; i <= n; ++i)

        X.f[i] = i, Y.f[i] = i, s[i] = g[i].size();

    for (x = n; x; --x)

        for (i = 0; i < s[x]; ++i)

            if (g[x][i] > x && (y = X.find(g[x][i])) ^ x)

                X.add(x, y), X.f[y] = X.fa[y][0] = x;

    for (x = 1; x <= n; ++x)

        for (i = 0; i < s[x]; ++i)

            if (g[x][i] < x && (y = Y.find(g[x][i])) ^ x)

                Y.add(x, y), Y.f[y] = Y.fa[y][0] = x;

    X.dfs(1), Y.dfs(n);

    for (i = 1; i <= n; ++i)

        val[X.dfn[i]] = Y.dfn[i];

    for (i = 1; i <= n; ++i)

        rt[i] = modify(rt[i - 1], 1, n, val[i]);

    while (Q--) {

        x = rd() + 1, y = rd() + 1, l = rd() + 1, r = rd() + 1;

        for (i = 19; ~i; --i)

            if (X.fa[x][i] >= l)

                x = X.fa[x][i];

        for (i = 19; ~i; --i)

            if (Y.fa[y][i] && Y.fa[y][i] <= r)

                y = Y.fa[y][i];

        printf(query(rt[X.dfn[x] - 1], rt[X.low[x]], 1, n, Y.dfn[y], Y.low[y]) ? "1\n" : "0\n");

    }

    return 0;

}

相关文章