【IOI 2018】Werewolf 狼人

虽然作为IOI的Day1T3，但其实不是一道很难的题，或者说这道题其实比较套路吧。

接下来讲解一下这个题的做法：

如果你做过NOI 2018的Day1T1，并且看懂了题面，那你很快就会联想到这道题，因为两者都是问某一个点能到达的点集，只不过限制在点上还是边上的问题。

$Kruskal$重构树可以把在边上的限制转化成点上的，于是能解决NOI 2018的Day1T1；那么这道题就可以直接做，因为限制已经在点上了。

具体来讲，从$s$点只能走编号$>=l$的点，那么我们就构建一棵树，使得任意一个非根节点的标号都比它父亲都大。要做到这一点，只要从大到小枚举点$x$，尝试把它加入树中，枚举所有与他相邻且编号比它大的节点$y$，如果$x$和$y$不在一个连通块里，就让$y$的并查集的根成为$x$的儿子，并在并查集里也连起来。

我们要对$s$和$t$都做一遍，也就是从大到小建一棵树$Tu$，从小到大建一棵树$Tv$。那么从$s$出发只走$>=l$的点能走到的点在$Tu$上就是一个子树；对$t$同理。

我们能用树上倍增找到$s$能走到的$Tu$上的那个子树，和$t$能走到的$Tv$的那个子树，这两者在两棵树上分别都对应$Dfs$序上的一段区间。

我们需要找到一个能变身的地点，它要满足能从$s$和$t$都能走到它，也就是在这两段$Dfs$上的区间中存在相同的元素。如何判断两个序列上的两个区间是否同时拥有某个元素，一般情况下我不会做，但是由于每个元素都恰好在一个序列中出现了一次，我们可以利用这个特殊的性质来解决。一个询问的答案是$1$当且仅当存在一个点，其中它在第一个序列中的位置在所求区间内，第二个序列也是。我们发现这就是一个简单的二维数点，我们把所有点在第一个和第二个$Dfs$序中中出现的位置分别当成$(x,y)$，一个询问就是判定一个二维平面上的一个矩形内是否有点。用离线树状数组实现比较方便。

$\bigodot$技巧&套路：

点上限制和$Kruskal$重构树在边上的限制的联系
两个$Dfs$序区间是否有相同元素向数点问题的转化

由于这道题本质是一道传统题，所以我用了传统的实现方法：

#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;

const int LOG = ;

const int N = ;

int n, m, nq, qi;

int ans[N];

vector<int> g[N];

struct Que {

  int x, y, id, ty, f;

  friend bool operator < (const Que &a, const Que &b) {

    return (a.x != b.x)? (a.x < b.x) : (a.ty < b.ty);

  }

} q[N * ];

struct Dsu {

  int fa[N];

  void Init(int n) {

    for (int i = ; i <= n; ++i) fa[i] = i;

  }

  int Sk(int x) {

    return fa[x] == x? x : fa[x] = Sk(fa[x]);

  }

} U, V;

struct Tree {

  vector<int> g[N];

  int tot, din[N], dfn[N], row[N], ed[N], dep[N], gr[LOG][N];

  void Add(int x, int y) {

    g[x].push_back(y), ++din[y];

  }

  void Dfs(int x) {

    dfn[x] = ++tot, row[tot] = x;

    for (int i = ; i < LOG; ++i)

      if (gr[i - ][x]) gr[i][x] = gr[i - ][gr[i - ][x]];

    for (int v : g[x]) {

      gr[][v] = x, dep[v] = dep[x] + ;

      Dfs(v);

    }

    ed[x] = tot;

  }

  void Build() {

    int rt = -;

    for (int i = ; i <= n; ++i) if (din[i] == ) rt = i;

    if (rt == -) throw;

    Dfs(rt);

  }

} Tu, Tv;

int Fly_u(int x, int lim) {

  for (int i = LOG - ; ~i; --i)

    if (Tu.gr[i][x] && Tu.gr[i][x] >= lim) x = Tu.gr[i][x];

  return x;

}

int Fly_v(int x, int lim) {

  for (int i = LOG - ; ~i; --i)

    if (Tv.gr[i][x] && Tv.gr[i][x] <= lim) x = Tv.gr[i][x];

  return x;

}

namespace BIT {

  int t[N];

  void Add(int x) {

    for (; x <= n; x += x & -x) ++t[x];

  }

  int Qr(int x, int r = ) {

    for (; x; x -= x & -x) r += t[x];

    return r;

  }

}

int main() {

  scanf("%d%d%d", &n, &m, &nq);

  for (int i = , x, y; i <= m; ++i) {

    scanf("%d%d", &x, &y);

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

  }

  U.Init(n), V.Init(n);

  for (int i = n; i >= ; --i) {

    for (int j : g[i]) {

      if (j < i) continue;

      int y = U.Sk(j);

      if (i != y) U.fa[y] = i, Tu.Add(i, y);

    }

  }

  for (int i = ; i <= n; ++i) {

    for (int j : g[i]) {

      if (j > i) continue;

      int y = V.Sk(j);

      if (i != y) V.fa[y] = i, Tv.Add(i, y);

    }

  }

  Tu.Build(), Tv.Build();

  for (int i = ; i <= n; ++i) {

    q[i].x = Tu.dfn[i], q[i].y = Tv.dfn[i];

    q[i].ty = ;

  }

  qi = n;

  for (int i = , x, y, l, r; i <= nq; ++i) {

    scanf("%d%d%d%d", &x, &y, &l, &r);

    ++x, ++y, ++l, ++r;

    int u = Fly_u(x, l), v = Fly_v(y, r);

    q[++qi] = (Que){ Tu.ed[u], Tv.ed[v], i, ,  };

    if (Tu.dfn[u] > ) q[++qi] = (Que){ Tu.dfn[u] - , Tv.ed[v], i, , - };

    if (Tv.dfn[v] > ) q[++qi] = (Que){ Tu.ed[u], Tv.dfn[v] - , i, , - };

    if (Tu.dfn[u] >  && Tv.dfn[v] > ) q[++qi] = (Que){ Tu.dfn[u] - , Tv.dfn[v] - , i, ,  };

  }

  sort(q + , q +  + qi);

  for (int i = ; i <= qi; ++i) {

    if (q[i].ty == ) {

      BIT::Add(q[i].y);

    } else {

      ans[q[i].id] += q[i].f * BIT::Qr(q[i].y);

    }

  }

  for (int i = ; i <= nq; ++i) {

    if (ans[i] < ) throw;

    printf("%d\n", (bool)ans[i]);

  }

  return ;

}

巴特西

【IOI 2018】Werewolf 狼人

最新文章

热门文章