Nemlit 的博客

Nemlit 的博客

By a konjac

题解 P4899 【[IOI2018] werewolf 狼人】

posted on 2019-10-14 21:27:21 | under 题解 |

感觉已经几次碰到这种类型的题目了,写篇 $Blog$ 总结一下

题意:

是否存在一条 $(s_i, t_i)$ 的路径,满足先只走编号不超过 $L_i$ 的点,再走编号不超过 $R_i$ 的点

$Solution$ :

对于这种限定经过点数的题目,可以比较自然地想到重构树:

由于前后都有限定,我们考虑建两颗重构树

第一颗按照边权为两个端点编号的最小值构建重构树,重构树每个点的点权 $x$ 表示不经过边权超过 $x$ 的边能到达的所有点;

第二颗则按照边权为两个端点最大值来构建重构树,重构树上每个点点权 $x$ 表示不经过边权 $≤x$ 的边能到达的所有点。

构建完重构树后,对于每一个 $s_i$ ,只需要在重构树上一直往上跳,找到一个点 $x$ ,满足 $L_i≤val_x$ 即可, $t_i$ 同理

这样我们会在两颗重构树上找到两个点,现在问题就转化成了:这两个点构成的子树中,有没有公共点(因为有公共点 $x$ 的话就肯定存在一条合法路径为 $s_i->x->t_i$ )

树上两个节点的交我们不太好做,考虑我们需要的是子树的交,对应在 $dfs$ 序中是一段区间,于是问题就进一步转化:

对于两个排列 $a, b$ ,每次询问排列 $a$ 在 $[l_1, r_1]$ 区间内,排列 $b$ 在 $[l_2, r_2]$ 区间内有无公共元素

其他题解到这一步怎么就是一句: 离线树状数组/在线主席树一下 就没了啊

由于两个数列都是排列,我们可以考律把排列 $a$ 映射到排列 $b$ 中去:

记 $gg[i]$ 表示 $i$ 这个元素在排列 $a$ 中出现的位置,于是我们可以得到一个 $gg[b[i]]$ 的一个新的排列,这个排列的意义为: $b_i$ 在 $a$ 中的出现位置

所以我们可以考律对 $gg[b[i]]$ 建一棵主席树(离线树状数组也行),每一个询问只需要查询在 $[l_2, r_2]$ 这些版本内, $[l_1, r_1]$ 有无元素即可

$Code:$

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define re register
il int read() {
    re int x = 0, f = 1; re char c = getchar();
    while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
    return x * f;
}
#define rep(i, s, t) for(re int i = s; i <= t; ++ i)
#define drep(i, s, t) for(re int i = t; i >= s; -- i)
#define Next(i, u) for(re int i = head[u]; i; i = e[i].next)
#define _ 400005
int n, m, fa[_], q, fr[_], to[_], head[_], cnt, gg[_], size[_ * 15], ls[_ * 15], rs[_ * 15], gk, rt[_];
struct Edge { int v, next; }e[_ << 1];
struct edge { int u, v, w; }E[_];
il void add(int u, int v) { e[++ cnt] = (Edge){v, head[u]}, head[u] = cnt; }
il bool cmp(edge a, edge b) { return a.w < b.w; }
il int find(int x) {
    while(x != fa[x]) x = fa[x] = fa[fa[x]];
    return x;
}
struct Tree {
    int L[_], R[_], pax, dfn[_], val[_], f[21][_];
    il void dfs(int u) {
        if(u <= n) L[u] = ++ pax, dfn[pax] = u, val[u] = u;
        else L[u] = pax + 1;
        rep(i, 1, 20) f[i][u] = f[i - 1][f[i - 1][u]];
        Next(i, u) f[0][e[i].v] = u, dfs(e[i].v);
        R[u] = pax;
    }
    il int find_pre(int x, int y) {
        drep(i, 0, 20) if(val[f[i][x]] >= y && f[i][x]) x = f[i][x];
        return x;
    }
    il int find_nxt(int x, int y) {
        drep(i, 0, 20) if(val[f[i][x]] <= y && f[i][x]) x = f[i][x];
        return x;
    }
}t1, t2;//重构树中用倍增找到我们需要的最高点
il void solve(Tree&t, int opt) {
    rep(i, 1, n * 2) fa[i] = i;
    int tot = n;
    rep(i, 1, m) {
        if(opt == 1) E[i] = (edge){fr[i], to[i], -min(fr[i], to[i])};
        if(opt == 2) E[i] = (edge){fr[i], to[i], max(fr[i], to[i])};
    }
    sort(E + 1, E + m + 1, cmp);
    rep(i, 1, m) {
        int u = E[i].u, v = E[i].v, a = find(u), b = find(v);
        if(a != b) fa[a] = fa[b] = ++ tot, t.val[tot] = abs(E[i].w), add(tot, a), add(tot, b);
    }
    t.dfs(tot);
}//构建重构树
il void insert(int &k, int kk, int l, int r, int ll) {
    if(!k) k = ++ gk; size[k] = size[kk] + 1;
    if(l == r) return;
    int mid = (l + r) >> 1;
    if(ll <= mid) insert(ls[k], ls[kk], l, mid, ll), rs[k] = rs[kk];
    else insert(rs[k], rs[kk], mid + 1, r, ll), ls[k] = ls[kk];
}
il int query(int k, int kk, int l, int r, int ll, int rr) {
    if(ll <= l && r <= rr) return size[kk] - size[k];
    int mid = (l + r) >> 1, ans = 0;
    if(ll <= mid) ans += query(ls[k], ls[kk], l, mid, ll, rr);
    if(mid < rr) ans += query(rs[k], rs[kk], mid + 1, r, ll, rr);
    return ans;
}//主席树求交
int main() {
    n = read(), m = read(), q = read();
    rep(i, 1, m) fr[i] = read() + 1, to[i] = read() + 1;
    solve(t1, 1), cnt = 0, memset(head, 0, sizeof(head)), solve(t2, 2);
    rep(i, 1, n) gg[t1.dfn[i]] = i;
    rep(i, 1, n) insert(rt[i], rt[i - 1], 1, n, gg[t2.dfn[i]]);
    while(q --) {
        int s = read() + 1, t = read() + 1, l = read() + 1, r = read() + 1, x = t1.find_pre(s, l), y = t2.find_nxt(t, r);
        printf("%d\n", query(rt[t2.L[y] - 1], rt[t2.R[y]], 1, n, t1.L[x], t1.R[x]) > 0);
    }
    return 0;
}

代码就凑合着看吧,我承认它非常丑,把它拆成及部分看的话也不是很难写