【IOI 2018】狼人（点权重构树 + 二维数点）

目录

• 题目
• 分析
• 实现

题目

【IOI 2018】狼人

给定 n n n 个点 m m m 条边的无向图， q q q 个询问，第 i i i 个询问形如 ( s i , e i , l i , r i ) (s_i, e_i, l_i, r_i) (si​,ei​,li​,ri​)，表示询问是否存在一条从 s i s_i si​ 出发后只经过 [ l i , n ] [l_i, n] [li​,n] 区间内的点，在 [ l i , r i ] [l_i, r_i] [li​,ri​] 中的某一点中变身，然后只经过 [ 1 , r i ] [1, r_i] [1,ri​] 区间内的点走到 t i t_i ti​ 的路径。

n ≤ 2 × 1 0 5 , m , q ≤ 4 × 1 0 5 n \le 2 \times 10^5, m, q \le 4 \times 10^5 n≤2×105,m,q≤4×105。允许离线。

分析

题目等价于：问从 s i s_i si​ 出发只经过 [ l i , n ] [l_i, n] [li​,n] 区间内的点能到达的点集与从 t i t_i ti​ 点出发只经过 [ 1 , r i ] [1, r_i] [1,ri​] 区间内的点能到达的点集是否有交。

看到这个题，你可能会联想到 NOI 2018 D1 T1 \text{NOI 2018 D1 T1} NOI 2018 D1 T1 归程。这两个题目都是询问从某点出发能到达的点集，他们的不同在于限制是在点上还是在边上。所以 NOI 2018 D1 T1 \text{NOI 2018 D1 T1} NOI 2018 D1 T1 归程要用 Kruscal \text{Kruscal} Kruscal 重构树，而这题却要用另一种重构树（可以暂时叫他点权重构树）。

我们希望从 s s s 点出发只经过 ≥ l \ge l ≥l 的点到达的点集对应这棵树的一个子树。那么我们就让树中的每个点的父亲都比他小。具体的做法是维护一个并查集，倒序把点添加进树中，每次枚举与之相邻并且大于它的所有点，如果它和自己不在一个联通块内，则把它所在联通块的根和自己连一条边，并且把它所在联通块根的父亲设为自己。于是每次我们就能通过倍增找到对应的子树了。

对于 ≥ l \ge l ≥l 和 ≤ r \le r ≤r 的限制都建一棵树（第二棵树与第一棵相反，树中的每个点的父亲都比他大。实现时应该按顺序添加点，并枚举小于它的点。）对于每个 s s s 和 e e e，通过倍增找到对应的子树 s ′ , e ′ s', e' s′,e′后，询问就变成了：每次询问两棵树的两个子树中是否有相同的点。

发现每个点只在两棵树中分别出现一次。记点 u u u 在第 i i i 棵树中的 dfs \text{dfs} dfs 序为 l i , u l_{i, u} li,u​，它子树中的 dfs 序 \text{dfs} 序 dfs序 最大为 r i , u r_{i, u} ri,u​。把它看作一个坐标为 ( l 1 , u , l 2 , u ) (l_{1, u}, l_{2, u}) (l1,u​,l2,u​) 的点，每次询问就变成了查询 x x x 坐标在区间 [ l 1 , s ′ , r 1 , s ′ ] [l_{1, s'}, r_{1, s'}] [l1,s′​,r1,s′​]， y y y 坐标在区间 [ l 2 , e ′ , r 2 , e ′ ] [l_{2, e'}, r_{2, e'}] [l2,e′​,r2,e′​] 内是否有点。使用常规的二维数点方法即可。时间复杂度 Θ ( n log ⁡ 2 n ) \Theta(n \log_2 n) Θ(nlog2​n)。

实现

我因为太懒所以直接分别手写了两棵树，实际上是可以合并起来写的，只需改一改比较函数即可。注意数组的大小 —— 无向图的边数是 2 × m 2 \times m 2×m，二维数点部分的操作个数是 4 × q + n 4 \times q + n 4×q+n。还有 IOI \text{IOI} IOI 题目的标号一般是从零开始，根据我的代码习惯会把它 + 1 +1 +1；输入输出方式类似 TopCoder \text{TopCoder} TopCoder，有兴趣的读者可以自行研究。

#include <cstdio>
#include <vector>
#include <algorithm>
#include "werewolf.h"
using namespace std;

const int maxn = 2e5 + 5, maxm = 4e5 + 5, maxk = 8e5 + 5, maxq = 2e6 + 5, logn = 20;
int n, m, q, k, u[maxm], v[maxm], s[maxm], e[maxm], l[maxm], r[maxm], bit[maxn];
int tot, ter[maxk], nxt[maxk], lnk[maxn], fa1[maxn], fa2[maxn], ans[maxm];
int tot1, ter1[maxn], nxt1[maxn], lnk1[maxn], dfn1, l1[maxn], r1[maxn], f1[maxn][logn];
int tot2, ter2[maxn], nxt2[maxn], lnk2[maxn], dfn2, l2[maxn], r2[maxn], f2[maxn][logn];

struct query {
    int id, type, x, y, z;
    query(int id = 0, int type = 0, int x = 0, int y = 0, int z = 0): id(id), type(type), x(x), y(y), z(z) {}

    friend bool operator<(query a, query b) {
        return a.x == b.x ? a.type < b.type : a.x < b.x;
    }
} qry[maxq];

void addEdge(int u, int v) {
    ter[++tot] = v;
    nxt[tot] = lnk[u];
    lnk[u] = tot;
}

void addEdge1(int u, int v) {
    ter1[++tot1] = v;
    nxt1[tot1] = lnk1[u];
    lnk1[u] = tot1;
}

void addEdge2(int u, int v) {
    ter2[++tot2] = v;
    nxt2[tot2] = lnk2[u];
    lnk2[u] = tot2;
}

int find1(int x) {
    return fa1[x] == x ? x : fa1[x] = find1(fa1[x]);
}

int find2(int x) {
    return fa2[x] == x ? x : fa2[x] = find2(fa2[x]);
}

void dfs1(int u, int p = 0) {
    l1[u] = r1[u] = ++dfn1;
    f1[u][0] = p;
    for (int i = 0; f1[f1[u][i]][i]; i++) {
        f1[u][i + 1] = f1[f1[u][i]][i];
    }
    for (int i = lnk1[u], v; i; i = nxt1[i]) {
        v = ter1[i];
        dfs1(v, u);
        r1[u] = r1[v];
    }
}

void dfs2(int u, int p = 0) {
    l2[u] = r2[u] = ++dfn2;
    f2[u][0] = p;
    for (int i = 0; f2[f2[u][i]][i]; i++) {
        f2[u][i + 1] = f2[f2[u][i]][i];
    }
    for (int i = lnk2[u], v; i; i = nxt2[i]) {
        v = ter2[i];
        dfs2(v, u);
        r2[u] = r2[v];
    }
}

int jump1(int u, int k) {
    for (int i = 18; i >= 0; i--) {
        if (f1[u][i] && f1[u][i] >= k) {
            u = f1[u][i];
        }
    }
    return u;
}

int jump2(int u, int k) {
    for (int i = 18; i >= 0; i--) {
        if (f2[u][i] && f2[u][i] <= k) {
            u = f2[u][i];
        }
    }
    return u;
}

void add(int x) {
    for (int i = x; i <= n; i += i & -i) {
        bit[i]++;
    }
}

int sum(int x) {
    int s = 0;
    for (int i = x; i >= 1; i -= i & -i) {
        s += bit[i];
    }
    return s;
}

vector<int> check_validity(int _n, vector<int> _x, vector<int> _y, vector<int> _s, vector<int> _e, vector<int> _l, vector<int> _r) {
    n = _n, m = _x.size(), q = _s.size();
    for (int i = 1; i <= m; i++) {
        u[i] = _x[i - 1] + 1;
        v[i] = _y[i - 1] + 1;
        addEdge(u[i], v[i]);
        addEdge(v[i], u[i]);
    }
    for (int i = 1; i <= q; i++) {
        s[i] = _s[i - 1] + 1;
        e[i] = _e[i - 1] + 1;
        l[i] = _l[i - 1] + 1;
        r[i] = _r[i - 1] + 1;
    }
    for (int i = 1; i <= n; i++) {
        fa1[i] = fa2[i] = i;
    }
    for (int i = n; i >= 1; i--) {
        for (int j = lnk[i], v; j; j = nxt[j]) {
            v = ter[j];
            if (v < i) continue;
            int a = find1(v);
            if (a == i) continue;
            fa1[a] = i;
            addEdge1(i, a);
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = lnk[i], v; j; j = nxt[j]) {
            v = ter[j];
            if (v > i) continue;
            int a = find2(v);
            if (a == i) continue;
            fa2[a] = i;
            addEdge2(i, a);
        }
    }
    dfs1(1), dfs2(n);
    for (int i = 1; i <= n; i++) {
        qry[++k] = query(-1, 1, l1[i], l2[i], -1);
    }
    for (int i = 1; i <= q; i++) {
        int S = jump1(s[i], l[i]), E = jump2(e[i], r[i]);
        qry[++k] = query(i, 2, r1[S], 1, r2[E]);
        qry[++k] = query(i, 2, r1[S], -1, l2[E] - 1);
        qry[++k] = query(i, 2, l1[S] - 1, -1, r2[E]);
        qry[++k] = query(i, 2, l1[S] - 1, 1, l2[E] - 1);
    }
    sort(qry + 1, qry + k + 1);
    for (int i = 1; i <= k; i++) {
        if (qry[i].type == 1) {
            add(qry[i].y);
        } else {
            ans[qry[i].id] += qry[i].y * sum(qry[i].z);
        }
    }
    vector<int> res;
    for (int i = 1; i <= q; i++) {
        res.push_back(ans[i] > 0);
    }
    return res;
}