题解：P11265 【模板】静态区间半群查询

· · 题解

来点 u 选科技！

原文：并查集线段树。

尝试改造一下 zkw 线段树，我们知道 zkw 线段树的区间查询就是 l,r 同时往上跳，并在这一过程中把包含在 (l,r) 中的信息加入答案（具体的，当 l 是偶数是将其兄弟加入答案，当 r 是奇数时也将其兄弟加入答案）。

得益于堆式存储，我们有几条可以利用的性质：首先，一次查询 (l,r) 中最终 l,r 的位置是固定且可以很快算出的（l,r 的 lca 就是它们在二进制下的 lcp）；并且，l 在向上跳的过程中遇到的每个节点的贡献都是固定的，r 也是如此。于是我们将静态区间半群查询转化成了静态叶子-祖先路径半群查询。

离线后，对 lca 从深到浅做扫描线，可以使用带权并查集维护每个叶子到当前根的半群信息，更新时暴力从儿子往父亲连边即可，并且这个并查集是可以带路径压缩的。

那我缺的按秩合并这块谁给我补啊？实际上你可以发现，因为我们总是把儿子连到父亲上，所以如果我们直接钦定一个点的秩为它的高度，则连边的过程和按秩合并是几乎一样的，于是时间复杂度分析也可以套用。由此我们得到了一个很好写的 \Theta(n \alpha(n)) 离线静态区间半群查询。

不知道为啥跑的不快，难过了。

using info = pair<mat, mat>;
info mul(const info& x, const info& y) { return {mul(x.first, y.first), mul(y.second, x.second)}; }

constexpr int kN = 1e6 + 2, kL = 21;

int n, m, q, ans, f[kN * 4];
mat a[kN];
info e[kN * 4], vf[kN * 4];
vector<pair<int, int>> rq[kL];

int F(int x) {
  if (!f[x]) {
    return x;
  }
  vf[x] = mul(vf[x], vf[exchange(f[x], F(f[x]))]);
  return f[x];
}

signed main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> q, rnd.init(), out.init();
  for (int i = 1; i <= n; ++i) rnd.genmat(a[i]);
  m = (1 << __lg(n + 1) + 1);
  auto _e = [](int i) -> mat& { return (i & 1) ? e[i ^ 1].first : e[i ^ 1].second; };
  for (int i = 1; i <= n; ++i) {
    _e(m + i) = a[i];
  }
  for (int i = m - 1; i >= 1; --i) {
    _e(i) = mul(e[i * 2 + 1].second, e[i * 2].first);
  }
  for (int i = 1, l, r; i <= q; ++i) {
    rnd.genqry(l, r, n);
    l += m - 1, r += m + 1;
    rq[__lg(l ^ r)].emplace_back(l, r);
  }
  for (int i = __lg(m); i; --i) {
    for (auto [l, r] : rq[__lg(m) - i]) {
      F(l), F(r);
      out.setres(mul(vf[l].first, vf[r].second));
    }
    for (int j = (1 << i); j < (1 << i + 1); ++j) {
      f[j] = j / 2, vf[j] = e[j];
    }
  }
  return cout << out.ans << endl, 0;
}