OfflineDynamicConnectivity

need RollBackUnionFind

struct OfflineDynamicConnectivity {
  int n;
  std::vector<std::array<int, 4>> edges;

  OfflineDynamicConnectivity(int n) : n(n) {
    assert(n > 0);
  }

  void addEdge(int l, int r, int u, int v) {
    assert(0 <= u && u < n && 0 <= v && v < n);
    edges.push_back({l, r, u, v});
  }

  [[nodiscard]] std::vector<bool> solve(const std::vector<std::pair<int, int>>& qrs) const {
    int q = int(qrs.size());
    assert(q > 0);
    std::vector<std::vector<std::pair<int, int>>> seg(2 * q - 1);
    for (const auto& [l, r, u, v] : edges) {
      assert(0 <= l && l <= r && r <= q);
      if (l == r) {
        continue;
      }
      auto dfs = [&](auto&& dfs, int x, int xl, int xr) -> void {
        if (l <= xl && xr <= r) {
          seg[x].emplace_back(u, v);
          return;
        }
        int xm = xl + (xr - xl) / 2;
        if (l < xm) {
          dfs(dfs, x + 1, xl, xm);
        }
        if (xm < r) {
          dfs(dfs, x + 2 * (xm - xl), xm, xr);
        }
      };
      dfs(dfs, 0, 0, q);
    }
    RollBackUnionFind rbuf(n);
    std::vector<bool> res(q);
    auto dfs = [&](auto&& dfs, int x, int l, int r) -> void {
      for (const auto& [u, v] : seg[x]) {
        rbuf.unite(u, v);
      }
      if (r - l == 1) {
        res[l] = (rbuf.find(qrs[l].first) == rbuf.find(qrs[l].second));
      } else {
        int m = l + (r - l) / 2;
        dfs(dfs, x + 1, l, m);
        dfs(dfs, x + 2 * (m - l), m, r);
      }
      rbuf.rollBack(seg[x].size());
    };
    dfs(dfs, 0, 0, q);
    return res;
  }
};