【Codeforces 1083C】Max Mex（线段树 & LCA）

Description

给定一颗 \(n\) 个顶点的树，顶点 \(i\) 有点权 \(p_i\)。其中 \(p_1,p_2,\cdots, p_n\) 为一个 \(0\sim (n-1)\) 的一个排列。

有 \(q\) 次操作，每次操作：

\(\texttt{1 x y}\)：交换 \(x, y\) 两顶点的点权；
\(\texttt{2}\)：求树上所有路径上的点权构成的集合的 \(\text{MEX}\) 中最大的。其中 \(S\) 集合的 \(\text{MEX}\) 为其中最小的没有在 \(S\) 中出现过的自然数。

Hint

\(1\le n, q\le 2\times 10^5\)。

Solution

线段树与树的船新结合，orz。

在所有路径的 \(\text{MEX}\) 中，若出现过 \(\text{MEX}=x\)，那么说明存在一条路径，上面出现了 \(0, 1, \cdots, (x-1)\) 所有这些点权。考虑到题目中 \(p\) 为一个排列，那么一个特定的点权只存在一个点与之对应，这给我们提供的很大的方便。

维护 \(\text{MEX}\)，根据经验可以考虑对权值建立线段树。然后我们发现满足 \(\text{MEX} = x\) 的极小路径最多只有一条，于是可以让线段树的一个结点直接维护一条路径。具体来讲，对于值域区间 \([l, r]\) 的线段树结点，维护一条路径 \(s\to t\) 满足路径上包含了 \(l, (l+1), \cdots , r\) 所有这些权值，并且 \(s\to t\) 是最小的满足这个条件的路径。

如何实现两个结点的合并？假设左右儿子对应的路径分别为 \(s_l\to t_l, s_r\to t_r\)，然后我们需要找到最小的一条同时包含这两条路径的路径，当然要注意可能不存在。

既然最小，毫无疑问就是取 \(s_l, s_r, t_l, t_r\) 这四个端点的其二作为新端点 \(s, t\)，其余两个都必须位于路径 \(s\to t\) 上。于是枚举这两个小端点就完事了，反正是常数级别。

接下来只要做到快速判断一个点 \(x\) 是否位于路径 \(s\to t\) 即可。首先 \(x\) 必须是顶点 \(s, t\) 至少其中一个的祖先（或本身），然后 \(x\) 还不得高于 \(\text{LCA}(s, t)\)。总之需要满足——

\[((\text{LCA}(s, x)=x)\or (\text{LCA}(t, x)=x))\land(\text{LCA}(s, t)=\text{LCA}(x, \text{LCA}(s, t)))
\]

由于这里求 \(\text{LCA}\) 的次数较多，于是尽量用较快的求法（ST 表，树剖）。

然后是查询。不难发现这玩意有可二分性，那么就二分答案 \(x\)，然后判断包含 \([0, x)\) 的路径是否存在即可。但这样是一次 \(O(\log^2 n)\)，虽说应该也可以但我们有 \(O(\log n)\) 的方法。

考虑线段树上二分，在这里我们还需要在线段树上走是，维护一下前面一段 \([0, x)\) 对应的路径 \(P\)。

具体地，对于一个结点，先看看自己当前值域下的路径，如果存在，那么尝试能不能将这个路径直接和 \(P\) 合并。如果可以我们就直接走掉。

不行的话，就考虑左区间是否存在覆盖整段左值域区间的路径。如果没有，那么右边自然不必考虑，因为前面不连续，后半再连续也毫无意义；反之如果左边有，那么再考虑右边，之后就是递归的事了。

于是这道题就 \(O((n+q)\log n)\) AC 了（LCA 使用 ST 表）。

Code

/*

 * Author : _Wallace_

 * Source : https://www.cnblogs.com/-Wallace-/

 * Problem : Codeforces 1083C Max Mex

 */

#include <array>

#include <algorithm>

#include <cctype>

#include <cstdio>

#include <vector>

#include <utility>

using namespace std;

const int N = 4e5 + 5;

const int logN = 20;

inline int read() {

  int x = 0; char c; while (!isdigit(c = getchar()));

  do x = (x << 1) + (x << 3) + c - 48; while (isdigit(c = getchar()));

  return x;

}

int n, m, fa[N];

int val[N], loc[N];

vector<int> adj[N];

namespace LCA {

  int fir[N], dep[N], lg2[N], timer = 0;

  pair<int, int> f[N][logN];

  void dfs(int x) {

    f[fir[x] = ++timer][0] = make_pair(dep[x] = dep[fa[x]] + 1, x);

    for (auto y : adj[x]) if (y != fa[x]) dfs(y), f[++timer][0] = make_pair(dep[x], x);

  }

  void init() {

    dfs(1), lg2[0] = -1;

    for (int i = 1; i <= timer; i++) lg2[i] = lg2[i >> 1] + 1;

    for (int j = 1; j < logN; j++) for (int i = 1; i + (1 << j) - 1 <= timer; i++)

      f[i][j] = min(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);

  }

  int get(int x, int y) {

    if (x <= 0 || y <= 0) return 0;

    x = fir[x], y = fir[y]; if (x > y) swap(x, y);

    int t = lg2[y - x + 1];

    return min(f[x][t], f[y - (1 << t) + 1][t]).second;

  }

}

bool in_path(int s, int t, int x) {

  int l = LCA::get(s, t);

  return (x == LCA::get(s, x) || x == LCA::get(t, x))

      && (l == LCA::get(x, l));

}

typedef array<int, 2> Path;

const Path emp = {-1, -1};

namespace segt {

  #define mid ((l + r) >> 1)

  Path dat[N << 2];

  Path merge(Path a, Path b) {

    if (a == emp || b == emp) return emp;

    for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) {

      int s = a[i], t = b[j], p = a[i ^ 1], q = b[j ^ 1];

      if (in_path(s, t, p) && in_path(s, t, q)) return {s, t};

    }

    if (in_path(a[0], a[1], b[0]) && in_path(a[0], a[1], b[1])) return a;

    if (in_path(b[0], b[1], a[0]) && in_path(b[0], b[1], a[1])) return b;

    return emp;

  }

  void build(int x, int l, int r) {

    if (l == r) { dat[x] = {loc[l], loc[l]}; return; }

    build(x << 1, l, mid), build(x << 1 | 1, mid + 1, r);

    dat[x] = merge(dat[x << 1], dat[x << 1 | 1]);

  }

  void fix(int x, int l, int r, int p) {

    if (l == r) { dat[x] = {loc[l], loc[l]}; return; }

    (p <= mid) ? fix(x << 1, l, mid, p) : fix(x << 1 | 1, mid + 1, r, p);

    dat[x] = merge(dat[x << 1], dat[x << 1 | 1]);

  }

  int query(int x, int l, int r, Path& p) {

    if (dat[x] != emp) {

      if (p == emp) { p = dat[x]; return r + 1; }

      Path f = merge(p, dat[x]);

      if (f != emp) { p = f; return r + 1; }

    }

    if (l == r) return l;

    int ret = query(x << 1, l, mid, p);

    if (ret <= mid) return ret;

    else return query(x << 1 | 1, mid + 1, r, p);

  }

  #undef mid

}

signed main() {

  n = read();

  for (int i = 1; i <= n; i++) loc[val[i] = read()] = i;

  for (int i = 2; i <= n; i++) adj[fa[i] = read()].push_back(i);

  LCA::init(), segt::build(1, 0, n - 1);

  m = read();

  while (m--) {

    int opt = read();

    if (opt == 1) {

      int x = read(), y = read();

      swap(loc[val[x]], loc[val[y]]), swap(val[x], val[y]);

      segt::fix(1, 0, n - 1, val[x]), segt::fix(1, 0, n - 1, val[y]);

    } else {

      Path tmp = emp;

      printf("%d\n", segt::query(1, 0, n - 1, tmp));

    }

  }

}

【Codeforces 1083C】Max Mex（线段树 & LCA）

Description

Hint

Solution

Code