省流：静态区间半群信息查询的离线 $O(n\alpha(n))$ 简单算法（核心代码 1.2k，默认 $n,m$ 同阶）。
众所周知静态区间半群信息查询的正常做法有一个在线的 $O(n\alpha(n))$ 做法，但那个东西十分的不 practical，同时空间也有点危险。如果允许离线，我们有一个扫描线+并查集的简单做法，但那个做法的复杂度是 $O(n\log n)$（元素顺序有要求导致无法按秩），实测也跑得不快。我们这里提出一种 $O(n\alpha(n))$ 的简单算法来解决这个问题。默认读者已经掌握了带权并查集和 zkw 线段树。
考察 zkw 线段树的查询结构（左闭右开 0-index 区间）：先将 l 加上 M，再将 r 加上 M+1，随后重复以下流程直到 l 与 r 成为兄弟，每次结束后将 l 与 r 减半：若 l 为偶数则将其兄弟置入贡献节点左序列的末端，若 r 为奇数则将其兄弟置于贡献节点右序列的首段。最后拼接左右贡献序列，我们即按序得到了所有的贡献节点，将其从左至右累计贡献即可。如果写过 zkw 线段树的代码，这段应当不难理解。
不难注意到，zkw 线段树堆式存储的特性为我们带来了另一条优秀性质：叶子 l 与叶子 r（保证其不相同且不为兄弟）的 lca 的两个儿子分别为 l>>__lg(l^r) 与 r>>__lg(l^r)，且这两个节点是兄弟。证明就是考虑这俩的 lcp 之后的长度是 __lg(l^r)。我们同时考虑，对于同一个节点作为路径上的 l 或 r 存在，它能造成的贡献各自是固定的。以 l 为例，若这个节点编号是奇数则没有贡献，否则是其兄弟的值。于是我们把一个节点的两种贡献打包成一个 pair（注意两项转移顺序一正一反），然后问题转化为线段树上叶子到某个已知的祖先（不含）的路径查半群。线段树的性质实在有点美妙，我们可以倒序枚举祖先然后用带权并查集处理这个东西，动态把每个点和爹连起来就行。注意一个细节：由于我们本质上是要找一个拓扑序，而同层节点之间没有祖孙关系，我们可以把 l 和 r 一起挂到深度上然后以层为单位处理，当然这个搞不搞都意义不大。
兜兜转转最后还是绕回了我们的并查集算法，那么它的复杂度为什么是对的呢？我们参考 OI-wiki 上的并查集复杂度证明，发现单路压所缺失的那个秩，它一共只有以下几个事情：
每次合并至多只有一个点的秩上升，且至多上升 1。
节点的秩不减。
一个点父亲的秩至少比自己的秩大一。
初始时，每个点会给势能带来 $\alpha(n)$ 倍秩的贡献。
我们充分发扬人类智慧，直接在线段树上取一个点到最近的叶子的距离作为秩锁死，来验证一下上面几条：
1，2：秩根本没变。
3：一个节点的父亲一定是某个祖先（因为每次连边都是一个点连它爹），到叶子的距离一定更大。
4：设底层有 $n=2^h$ 个节点，那总秩为 $\sum_{i=0}^h(i\times2^{h-i})=\sum_{i=0}^{h-1}\sum_{j=0}^{i}2^j=\sum_{i=1}^{h}(2^i-1)=2^{h+1}-h-2=O(n)$，于是初始势能正确。
于是我们证明了这个东西的复杂度是正确的！代码非常好写。
#if __cplusplus >= 202002L
#define TEMPLATE \
template <class S, auto op, auto e> \
requires is_convertible_v<decltype(op), function<S(S, S)>> && \
is_convertible_v<decltype(e), function<S()>>
#else
#define TEMPLATE template <class S, S (*op)(S, S), S (*e)()>
#endif
TEMPLATE class uttree {
typedef pair<S, S> S_p;
static auto e_p() { return make_pair(e(), e()); }
static auto op_p(S_p x, S_p y) {
return make_pair(op(x.first, y.first), op(y.second, x.second));
}
vector<S_p> sgt;
public:
void build(const vector<S>& v) {
int n = v.size(), M = 1 << (__lg(n + 1) + 1);
sgt.resize(M << 1, e_p());
auto vi = [&](int i) -> S& {
return i & 1 ? sgt[i ^ 1].first : sgt[i ^ 1].second;
};
for (int i = 1; i <= n; ++i) vi(i + M) = v[i - 1];
for (int i = M - 1; i > 1; --i)
vi(i) = op(sgt[i << 1 | 1].second, sgt[i << 1].first);
}
uttree() {}
explicit uttree(const vector<S>& v) { build(v); }
vector<S> operator()(const vector<pair<int, int>>& q) const {
if (q.empty()) return {};
int n = q.size(), M = sgt.size() >> 1, h = __lg(M);
vector<vector<int>> tog(h);
vector<int> fa(M << 1, -1);
vector<S_p> fv(M << 1, e_p());
vector<S> ans(n, e());
for (int i = 0; i < n; ++i) {
int l = q[i].first + M, r = q[i].second + M + 1;
tog[__lg(l ^ r)].push_back(i);
}
auto findf = [&](auto&& self, int x) {
int f = fa[x];
if (!~f) return x;
fa[x] = self(self, f);
fv[x] = op_p(fv[x], fv[f]);
return fa[x];
};
for (int z = h; z; --z) {
for (int i : tog[h - z]) {
int l = q[i].first + M, r = q[i].second + M + 1;
findf(findf, l), findf(findf, r);
ans[i] = op(fv[l].first, fv[r].second);
}
for (int x = 1 << z; x < (1 << (z + 1)); ++x)
fa[x] = x >> 1, fv[x] = sgt[x];
}
return ans;
}
};
TEMPLATE vector<S> query(const vector<S>& v, const vector<pair<int, int>>& q) {
return uttree<S, op, e>{v}(q);
}以上。精细复杂度分析可以进一步说明复杂度是 $O((n+m)\alpha(m,n))$ 的，不再赘述。
发出一天后 @critnos 指出这东西可以上树，咕了几天之后 ut 把代码写了出来，这里是一篇介绍。（不过上树方式其实不太一样？）方便起见，本文考虑的是静态树上路径半群，信息在点上。边没啥区别。
这里提一嘴 cnos 的原始方案吧，就是注意到线段树的架构只要是个比较正常的平衡的二叉树都可以，于是我们直接换成 GBST 莽上去，就可以了。这个东西的问题是细节高低有点烦人……于是 ut 选择了一种码量更大但是思路更加自然的做法。
我们对树进行重链剖分。对每个点连边到链顶的父亲连边构成新树，边权是自己到链顶所有信息复合起来。不难注意到两边走到同一条链上之后就只剩一个区间，化归为链上的问题。
好那么我们考虑怎么直接通过这棵新树来定位这俩点。如果两个查询点在新树上存在祖先-后代关系直接定位完了，否则考虑其各自到 lca 前的最后一个祖先，如果它们在同一重链上就是这俩；否则，说明这俩在进同一条重链的时候正好进到了同一个点，需要的信息就是这个点的点权，也不需要再查了。至于这俩祖先的定位和各自的路径信息，我们可以小改一下求 LCA 的那个 Tarjan 算法，带个权就能做了。
兜兜转转绕回了和原树上 Tarjan 差不多的东西，于是保留节目之复杂度证明。我们定义一个点的秩固定为其在新树上到最远的叶子的距离（从 0 开始）。那么我们只需要证明初始全局秩和是 $O(n)$ 的就可以了。
我们归纳证明这个事情：对于秩为 $h$ 的点，其在原树上的子树大小至少为 $2^{h+1}-1$。比较平凡，在此略去。于是我们不难注意到一个秩为 $h$ 的点去掉重儿子后的子树大小至少为 $2^h$，称这些点属于这个秩为 $h$ 的点的“管辖范围”。不难注意到等秩的不同点“管辖范围”不交（否则在新树上一定有一个是另一个的祖先，与“等秩”矛盾），于是这样的点数至多有 $\frac n{2^h}$，然后就可以类似线段树证了。
代码……额不太短，但依然比较好写，ut 过编后板子一个字节都没改就过了。另外需要去上一篇里把那个序列板子薅过来。
这次真不如 Tarjan 快了。
TEMPLATE class uttree_hlc_node {
typedef pair<S, S> S_p;
static S_p e_p() { return make_pair(e(), e()); }
static S_p op_p(S_p x, S_p y) {
return make_pair(op(x.first, y.first), op(y.second, x.second));
}
static S op3(S x, S y, S z) { return op(op(x, y), z); }
uttree<S_p, uttree_hlc_node<S, op, e>::op_p, uttree_hlc_node<S, op, e>::e_p>
seq;
vector<int> dfn, tf, top;
vector<vector<int>> es;
vector<S> vl;
vector<S_p> fw;
public:
void build(const vector<pair<int, int>>& v, const vector<S>& cv) {
int n = (vl = cv).size();
tf.resize(n), dfn.resize(n), top.resize(n);
es.resize(n + 1), fw.resize(n, e_p());
for (auto p : v) {
int u = p.first, v = p.second;
es[u].push_back(v), es[v].push_back(u);
}
vector<int> sn(n);
auto dfs1 = [&](auto&& self, int x) -> int {
int sx = 1, sz = 0;
for (int y : es[x]) {
if (y == tf[x]) continue;
tf[y] = x;
int sy = self(self, y);
if (sx += sy, sy > sz) sn[x] = y, sz = sy;
}
return sx;
};
tf[0] = n, dfs1(dfs1, 0);
int dt = 0;
vector<S_p> vl2(n, e_p());
auto dfs2 = [&](auto&& self, int x, int t, S_p sm) -> void {
fw[x] = sm = op_p(vl2[dfn[x] = dt++] = make_pair(vl[x], vl[x]), sm);
if (int z = sn[x]) {
self(self, z, t, sm);
for (int y : es[x])
if (y != tf[x] && y != z) self(self, y, y, e_p());
}
tf[x] = tf[top[x] = t];
};
dfs2(dfs2, 0, 0, e_p()), seq.build(vl2);
for (int i = 0; i < n; ++i) es[i].clear();
for (int i = 0; i < n; ++i) es[tf[i]].push_back(i);
}
uttree_hlc_node() {}
explicit uttree_hlc_node(const vector<pair<int, int>>& v,
const vector<S>& cv) {
build(v, cv);
}
vector<S> operator()(const vector<pair<int, int>>& q) const {
if (q.empty()) return {};
int n = dfn.size(), m = q.size();
vector<vector<int>> tog(n + 1);
vector<tuple<int, S, int, S>> ans(m, make_tuple(0, e(), 0, e()));
vector<S> res(m, e());
for (int i = 0; i < m; ++i) {
int x = q[i].first, y = q[i].second;
if (x == y) {
res[i] = vl[x];
continue;
}
tog[x].push_back(i), tog[y].push_back(i);
}
for (bool rev : {false, true}) {
vector<int> fa(n + 1, -1);
vector<S_p> fv(n + 1, e_p());
basic_string<bool> vst(n, false);
auto findf = [&](auto&& self, int x) {
int f = fa[x];
if (!~f) return x;
fa[x] = self(self, f);
fv[x] = op_p(fv[x], fv[f]);
return fa[x];
};
auto dfs = [&](auto&& self, int x) -> void {
vst[x] = true;
if (!rev)
for (int y : es[x]) self(self, y);
else
for (auto it = es[x].rbegin(); it != es[x].rend(); ++it)
self(self, *it);
for (int i : tog[x]) {
int tx = q[i].first, ty = q[i].second;
if (x == ty && vst[tx]) {
get<0>(ans[i]) = findf(findf, tx);
get<1>(ans[i]) = fv[tx].first;
}
if (x == tx && vst[ty]) {
get<2>(ans[i]) = findf(findf, ty);
get<3>(ans[i]) = fv[ty].second;
}
}
for (int y : es[x]) fa[y] = x, fv[y] = fw[y];
};
dfs(dfs, n);
}
vector<pair<int, int>> qry;
for (int i = 0; i < m; ++i) {
int x = q[i].first, y = q[i].second;
if (x == y) continue;
int fx = get<0>(ans[i]), fy = get<2>(ans[i]);
S &vx = get<1>(ans[i]), &vy = get<3>(ans[i]);
if (fx == tf[fy])
res[i] = op3(vl[x], fw[fy].second, vy);
else if (fy == tf[fx])
res[i] = op3(vx, fw[fx].first, vl[y]);
else if (top[fx] != top[fy])
res[i] = op3(op(vx, fw[fx].first), vl[tf[fx]], op(fw[fy].second, vy));
else {
int l = dfn[fx], r = dfn[fy];
if (l > r) swap(l, r);
qry.emplace_back(l, r + 1);
}
}
vector<S_p> ret = seq(qry);
for (int i = 0, j = 0; i < m; ++i) {
int x = q[i].first, y = q[i].second;
if (x == y) continue;
int fx = get<0>(ans[i]), fy = get<2>(ans[i]);
if (fx == tf[fy] || fy == tf[fx] || top[fx] != top[fy]) continue;
res[i] =
op3(get<1>(ans[i]), dfn[fx] < dfn[fy] ? ret[j].first : ret[j].second,
get<3>(ans[i]));
++j;
}
return res;
}
};
TEMPLATE vector<S> query(const vector<pair<int, int>>& v, const vector<S>& cv,
const vector<pair<int, int>>& q) {
return uttree_hlc_node<S, op, e>{v, cv}(q);
}以上。
鄂公网安备 42010202000505 号