单 log 并查集线段树分治

· · 个人记录

省流：标题。https://www.luogu.com.cn/problem/P5787 的单 log 做法，打不过双 log。

本质上我们要干这么一个事情：对于一条边，它会被拆到 log 个线段树节点上。我们希望这些节点上这条边合并的总复杂度是 O(\log n)。事实上并查集的结构告诉我们合并本身实际上是常数时间，我们只需要保证一个点在这样 log 个节点上执行 findf 总复杂度是一个 log 即可。

我们首先考虑魔改掉我们的并查集。当我们抵达一个线段树节点时，对其上的边进行 dfs/bfs，并把一个联通块的所有点连到这个联通块的起点（抛弃启发式合并）。我们发现同一个节点上所有边只会让一个点的深度至多增加一。

然后我们考虑在抵达一个线段树节点时，直接将其子树内所有涉及到的边执行 findf。由于我们的合并结构，一条边被执行 findf 的复杂度实际上就只有常数时间（不超过一）。于是我们就把这部分复杂度直接摊成了线段树区间加边的复杂度。于是这个东西就对了。

代码其实很好写。但是常数特别大，要卡评测机波动，也可能是实现问题。有一些看起来意义不明的数组和写法都是为了卡常。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 2e5 + 9, M = 1 << 18;
int n, m, k, fa[N], q[N], tog[N << 1];
vector<tuple<int, int, int, int, int, int>> sgt[M];
vector<int> es[N];
bool vst[N];
template <typename T>
void clear(vector<T>& v) {
  vector<T>().swap(v);
}
inline int findf(int x) { return fa[x] ?: x; }
void dfs(int w, int L, int R, int p) {
  int s = p, t = p, z = 0;
  for (auto [l, r, u, x, v, y] : sgt[w])
    if (r >= R && l <= L) {
      es[u].push_back(y), es[y].push_back(u), tog[z++] = u;
      es[v].push_back(x), es[x].push_back(v), tog[z++] = v;
    }
  for (int u : span(tog, z))
    if (!exchange(vst[u], true))
      for (q[t++] = u; s < t; ++s)
        for (int y : es[q[s]])
          if (!exchange(vst[y], true)) fa[q[t++] = y] = u;
  for (int x : span(q + p, t - p)) clear(es[x]), vst[x] = false;
  bool tg = true;
  for (auto [l, r, u, x, v, y] : sgt[w])
    if (r >= R && l <= L) tg &= findf(u) != findf(v);
  if (!tg)
    for (int i = L; i <= R; ++i) cout << "No" << '\n';
  else if (L == R)
    cout << "Yes" << '\n';
  else {
    int mid = (L + R) >> 1;
    for (auto [l, r, u, x, v, y] : sgt[w]) {
      if (r >= R && l <= L) continue;
      u = findf(u), v = findf(v), x = findf(x), y = findf(y);
      if (r > mid) sgt[w << 1 | 1].emplace_back(l, r, u, x, v, y);
      if (l <= mid) sgt[w << 1].emplace_back(l, r, u, x, v, y);
    }
    clear(sgt[w]), dfs(w << 1, L, mid, t), dfs(w << 1 | 1, mid + 1, R, t);
  }
  for (int x : span(q + p, t - p)) fa[x] = 0;
}
signed main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> m >> k;
  for (int x, y, l, r; m; --m) {
    if (cin >> x >> y >> l >> r, ++l > r) continue;
    sgt[1].emplace_back(l, r, x, x + n, y, y + n);
  }
  return dfs(1, 1, k, 0), cout << flush, 0;
}

以上。