10/21
23:25
OI

[IOI2018]狼人 [Kruskal重构树][主席树]

[IOI2018]狼人

Kruskal重构树是对边玩的,不过也可以对点玩,不新建点就行了。

建立两棵Kruskal重构树,那么可以求出从s,e出发,分别可以到达的所有> L, < R的点。

在重构树上标号,发现是连续序列,可以看作二维数点,主席树随便维护。

#include <bits/stdc++.h>
#include "werewolf.h"

const int N = 4e5 + 233;

int n;

std::vector<int> G[N];

struct Kruskal_Rebuild_Tree {
  int type, fa[N][21], ufs[N], dfn[N], size[N], num;

  std::vector<int> T[N];

  int find(int x) {
    return x == ufs[x] ? x : ufs[x] = find(ufs[x]);
  }

  void dfs(int x) {
    dfn[x] = ++num;
    size[x] = 1;

    for (int i = 1; i <= 20; ++i)
      fa[x][i] = fa[fa[x][i - 1]][i - 1];

    for (auto y : T[x]) {
      dfs(y);
      size[x] += size[y];
    }
  }

  int get(int x, int k) {
    for (int i = 20; ~i; --i)
      if (fa[x][i]) {
        if (type == 1) {
          if (fa[x][i] >= k)
            x = fa[x][i];
        } else {
          if (fa[x][i] <= k)
            x = fa[x][i];
        }
      }
    return x;
  }

  void build() {
    for (int i = 1; i <= n; ++i)
      ufs[i] = i;

    if (type == 1) {
      for (int x = n; x; --x)
        for (auto y : G[x])
          if (x < y) {
            int _x = find(x), _y = find(y);

            if (_x == _y)
              continue;

            T[_x].push_back(_y);
            fa[_y][0] = ufs[_y] = _x;
          }

      dfs(1);

    } else {
      for (int x = 1; x <= n; ++x)
        for (auto y : G[x])
          if (x > y) {
            int _x = find(x), _y = find(y);

            if (_x == _y)
              continue;

            T[_x].push_back(_y);
            fa[_y][0] = ufs[_y] = _x;
          }

      dfs(n);
    }
  }
} A, B;

struct Segment_Tree {
  int ls, rs, size;
} tree[N * 50];

int root[N], tot;

void change(int &now, int pre, int x, int L, int R) {
  tree[now = ++tot] = tree[pre];
  ++tree[now].size;
  if (L == R)
    return;
  int mid = (L + R) >> 1;
  if (x <= mid)
    change(tree[now].ls, tree[pre].ls, x, L, mid);
  else
    change(tree[now].rs, tree[pre].rs, x, mid + 1, R);
}

int query(int x, int y, int l, int r, int L, int R) {
  if (l <= L && r >= R)
    return tree[y].size - tree[x].size;
  int mid = (L + R) >> 1, ret = 0;
  if (l <= mid)
    ret += query(tree[x].ls, tree[y].ls, l, r, L, mid);
  if (r > mid)
    ret += query(tree[x].rs, tree[y].rs, l, r, mid + 1, R);
  return ret;
}

int id[N];

std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {

  n = N;

  for (int i = 0; i < X.size(); ++i) {
    int x = X[i] + 1, y = Y[i] + 1;
    G[x].push_back(y);
    G[y].push_back(x);
  }

  A.type = 1, A.build();
  B.type = -1, B.build();

  for (int i = 1; i <= n; ++i)
    id[A.dfn[i]] = B.dfn[i];
  for (int i = 1; i <= n; ++i)
    change(root[i], root[i - 1], id[i], 1, n);

  std::vector<int> ans;

  for (int i = 0; i < S.size(); ++i) {
    int s = S[i] + 1, e = E[i] + 1, l = L[i] + 1, r = R[i] + 1,
      x = A.get(s, l), y = B.get(e, r);

    ans.push_back((bool)(query(root[A.dfn[x] - 1], root[A.dfn[x] + A.size[x] - 1],
      B.dfn[y], B.dfn[y] + B.size[y] - 1, 1, n)));
  }
  return ans;
}