给定一个 $n$ 个点,$m$ 条边的森林,每次执行以下的操作:

  • Q x y k,查询 $x\rightarrow y$ 路径上点权第 $k$ 大。
  • L x y,连接 $x\rightarrow y$ 节点。

数据范围:$n\leq 8\times 10^4$

问题强制在线

考虑问题的弱化版,

这个思路的入门可以考虑笔者在博客园里写的一篇博客,Link

这道题,因为存在了动态加边,比较容易想到用启发式合并来维护,每次遍历的时候,顺便更新子树的所有信息即可。

那么启发式合并的我们定义为当前节点所在树的大小,这样比较好维护,虽然笔者并不认为这个复杂度正确。

时间复杂度 $\mathcal O (nlog^2n)$

注意数组空间,需要开到两个 $log$ 的级别。

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;
const int LOG = 20;

int ts, tt, n, m, disc_cnt, tot;
int disc[N], fa[N], siz[N], root[N], dep[N], a[N];
int ft[N][LOG + 1];
int ch[N * 300][2], sum[N * 300];
vector<int> g[N];

void modify(int& x, int pre, int l, int r, int p) {
  x = ++tot;
  sum[x] = sum[pre];
  ch[x][0] = ch[pre][0], ch[x][1] = ch[pre][1];
  if (l == r) {
    sum[x]++;
    return;
  }
  int mid = (l + r) >> 1;
  p <= mid ? modify(ch[x][0], ch[pre][0], l, mid, p) : modify(ch[x][1], ch[pre][1], mid + 1, r, p);
  sum[x] = sum[ch[x][0]] + sum[ch[x][1]];
}

int query(int x1, int x2, int x3, int x4, int l, int r, int k) {
  if (l == r) 
    return disc[l];
  int mid = (l + r) >> 1, s = sum[ch[x1][0]] + sum[ch[x2][0]] - sum[ch[x3][0]] - sum[ch[x4][0]];
  if (s >= k) 
    return query(ch[x1][0], ch[x2][0], ch[x3][0], ch[x4][0], l, mid, k);
  else 
    return query(ch[x1][1], ch[x2][1], ch[x3][1], ch[x4][1], mid + 1, r, k - s);
}

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

int lca(int u, int v) {
  if (dep[u] < dep[v])
    swap(u, v);
  for (int i = LOG; i >= 0; i--)
    if (dep[ft[u][i]] >= dep[v])
      u = ft[u][i];
  if (u == v)
    return u;
  for (int i = LOG; i >= 0; i--)
    if (ft[u][i] != ft[v][i])
      u = ft[u][i], v = ft[v][i];
  return ft[u][0];
}

void dfs(int u, int fa) {
  ft[u][0] = fa;
  dep[u] = dep[fa] + 1;
  siz[u] = 1;
  modify(root[u], root[fa], 1, disc_cnt, a[u]);
  for (int i = 1; i <= LOG; i++)
    ft[u][i] = ft[ft[u][i - 1]][i - 1];
  for (auto v : g[u]) 
    if (v ^ fa) {
      dfs(v, u);
      siz[u] += siz[v];
    }
}

signed main() {
  // freopen(".in", "r", stdin);
  scanf("%d %d %d %d", &ts, &n, &m, &tt);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    disc[i] = a[i];
  }
  sort(disc + 1, disc + 1 + n);
  disc_cnt = unique(disc + 1, disc + 1 + n) - disc - 1;
  for (int i = 1; i <= n; i++) {
    a[i] = lower_bound(disc + 1, disc + 1 + disc_cnt, a[i]) - disc;
  }
  for (int i = 1; i <= m; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    g[u].push_back(v);
    g[v].push_back(u);
  } 
  for (int i = 1; i <= n; i++) {
    fa[i] = i;
    if (!siz[i]) 
      dfs(i, 0);
  }
  for (int cs = 1, last_ans = 0, u, v, k; cs <= tt; cs++) {
    char opt[5];
    scanf("%s %d %d", &opt, &u, &v);
    u ^= last_ans, v ^= last_ans;
    if (opt[0] == 'Q') {
      scanf("%d", &k);
      k ^= last_ans; 
      int p = lca(u, v);
      // cerr << "debug : " << u << ' ' << v << ' ' << p << ' ' << a[u] << ' ' << a[v] << ' ' << a[p] << '\n';
      printf("%d\n", last_ans = query(root[u], root[v], root[p], root[ft[p][0]], 1, disc_cnt, k));
    } else {
      int p = get_fa(u), q = get_fa(v);
      if (siz[p] > siz[q])
        swap(u, v), swap(p, q);
      fa[p] = q, siz[q] += siz[p];
      g[v].push_back(u);
      g[u].push_back(v);
      dfs(u, v);
    }
  }
  return 0;
}

主要还是这种类型问题的解题思路,看到 $k$ 大还是考虑用可持久化线段树或者分治来维护,这里只能用可持久化线段树维护。

最后修改:2020 年 08 月 22 日 11 : 41 PM
如果觉得我的文章对你有用,请随意赞赏