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

题意:

当你是人形的时候你只能走 \([L,N-1]\) 的编号的点（即大于等于L的点）

当你是狼形的时候你只能走 \([1,R]\) 的编号的点（即小于等于R的点）

然后问题转化成人形和狼形能到的点有没有交集。

solution:

发现可以建 kruskal重构树，就可以通过在树上倍增来求出来一个子树，这个子树内是你可以到的点。然后问题转化成了两个子树区间的交，这个问题可以用主席树解决。

定义 \(rev1_i\) 是在树上的第 \(i\) 个位置对应的数，那你定义 \(r_{rev1_i}=i\)，那么 \(r_i\) 就是这个元素在树上出现的位置，\(rev2_i\)同理，即这个数在第二棵树上对应的数，然后主席树求解。

#include <bits/stdc++.h>

using namespace std;

int read() {

  int x = 0;

  char c = getchar();

  while (c < 48) c = getchar();

  while (c > 47) x = x * 10 + (c - 48), c = getchar();

  return x;

}

int n, m, q;

const int maxn = 4e5 + 54;

struct edge {

  int u, v;

};

vector<edge> e;

int fa[maxn];

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

vector<int> g[maxn];

struct Tree {

  int L[maxn], R[maxn], idx;

  int rev[maxn], val[maxn], f[maxn][22];

  void dfs(int u) {

    if (u <= n) {

      rev[L[u] = ++idx] = u;

      val[u] = u;

    } else

      L[u] = idx + 1;

    for (int i = 1; i <= 20; i++) f[u][i] = f[f[u][i - 1]][i - 1];

    for (int v : g[u]) f[v][0] = u, dfs(v);

    R[u] = idx;

  }

  int getu(int s, int l) {

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

      if (f[s][i] && val[f[s][i]] >= l) s = f[s][i];

    return s;

  }

  int getv(int t, int r) {

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

      if (f[t][i] && val[f[t][i]] <= r) t = f[t][i];

    return t;

  }

} t1, t2;

int tot;

int rt[maxn], ls[maxn << 5], rs[maxn << 5], val[maxn << 5], cnt = 0;

void upd(int& p, int pre, int l, int r, int x) {

  ls[p = ++cnt] = ls[pre], rs[p] = rs[pre], val[p] = val[pre] + 1;

  if (l == r) return;

  int mid = l + r >> 1;

  if (x <= mid)

    upd(ls[p], ls[pre], l, mid, x);

  else

    upd(rs[p], rs[pre], mid + 1, r, x);

}

int qry(int a, int b, int ql, int qr, int l, int r) {

  if (ql <= l && r <= qr) return val[b] - val[a];

  int mid = l + r >> 1, ans = 0;

  if (ql <= mid) ans = qry(ls[a], ls[b], ql, qr, l, mid);

  if (qr > mid) ans += qry(rs[a], rs[b], ql, qr, mid + 1, r);

  return ans;

}

int main() {

  n = read(), m = read(), q = read();

  for (int i = 0; i < m; i++) {

    int u = read(), v = read();

    ++u, ++v;

    if (u > v) u ^= v ^= u ^= v;

    e.push_back({ u, v });

  }

  for (int i = 1; i <= n * 2; i++) fa[i] = i, g[i].clear();

  sort(e.begin(), e.end(), [](edge a, edge b) { return a.u > b.u; });

  tot = n;

  for (auto x : e) {

    int u = find(x.u), v = find(x.v);

    if (u == v) continue;

    fa[u] = fa[v] = ++tot;

    t1.val[tot] = x.u;

    g[tot].push_back(u), g[tot].push_back(v);

  }

  t1.dfs(tot);

  for (int i = 1; i <= n * 2; i++) fa[i] = i, g[i].clear();

  sort(e.begin(), e.end(), [](edge a, edge b) { return a.v < b.v; });

  tot = n;

  for (auto x : e) {

    int u = find(x.u), v = find(x.v);

    if (u == v) continue;

    fa[u] = fa[v] = ++tot;

    t2.val[tot] = x.v;

    g[tot].push_back(u), g[tot].push_back(v);

  }

  t2.dfs(tot);

  vector<int> r(n + 1);

  for (int i = 1; i <= n; i++) r[t1.rev[i]] = i;

  for (int i = 1; i <= n; i++) upd(rt[i], rt[i - 1], 1, n, r[t2.rev[i]]);

  for (int i = 0; i < q; i++) {

    int s = read(), t = read(), l = read(), r = read();

    ++s, ++t, ++l, ++r;

    int u = t1.getu(s, l), v = t2.getv(t, r);

    if (qry(rt[t2.L[v] - 1], rt[t2.R[v]], t1.L[u], t1.R[u], 1, n))

      puts("1");

    else

      puts("0");

  }

  return 0;

}

巴特西

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

题意:

solution:

最新文章

热门文章