省流：静态区间半群信息查询的在线 $O(n)-O(\alpha(n))$ 简单算法（核心代码 1.6k）。

众所周知静态区间半群信息查询的正常做法有一个在线的 $O(n)-O(\alpha(n))$ 做法，但那个东西十分的不 practical。我们这里提出一种 $O(n)-O(\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（注意两项转移顺序一正一反），然后问题转化为线段树上叶子到某个已知的祖先（不含）的路径查半群。

我们这里定义：

$$\large{A(c,i,j)=}\begin{cases} j+1&if\ c=1\ and\ i=0\\[8pt] A(j,i-1,A(1,i-1,j))&if\ c=1\ and\ i>0\\[8pt] A(c-1,i,A(1,i,j))&if\ c>1\\[8pt] \end{cases}$$

人话就是把阿克曼函数迭代了 $c$ 次。这里我们要求 $1\le c\le j$。

我们不难观察到对于任意 $p\ge 1$，存在 $n$ 与 $x_1=1\lt x_2\lt\cdots\lt x_{n+1}=p$ 且存在 $b_1\gt b_2\gt\cdots\gt b_n$ 与 $1\le c_1,c_2,\cdots,c_n$ 满足 $x_{i+1}=A(c_i,b_i,x_i)$，且对于任意 $1\le i\le n$ 均有 $1\le c_i\le x_i$ 成立。证明的话对 $b$ 贪心即可。定义 $\alpha(p)$ 是满足 $A(1,i,1)\gt p$ 的最小整数值，那么不难发现 $0\le b_i\lt \alpha(p)$。换而言之，如果我们取所有如上合法的 $[x,A(c,b,x))$ 为区间，那我们可以将任何前缀用 $\alpha$ 个区间拼起来。

让我们回到原问题。重新定义一个线段树上节点到最近叶子的距离加一为其“高度”。我们对一个高度为 $h$ 的点维护所有，合法的、其上节点高度构成连续 $[h,A(c,b,h))$ 的、从这个点出发向根的，链上的半群。这个东西是显然可以用阿克曼定义式来递推的。

接着来算这个东西的状态数。我们的 $c$ 只有 $O(h)$ 种，$b$ 只有 $O(\alpha(n))$ 种（其实是 $\alpha(\log_2n)$ 种，但这俩同阶），于是总状态数的规模在 $\alpha(n)$ 倍所有节点高度和，而后者熟知是线性的，所以总的状态数是 $O(n\alpha(n))$ 的，于是预处理和空间复杂度显然是 $O(n\alpha(n))$ 的。至于查询，我们注意到高度构成的前缀本质上只有 $O(\log_2n)$ 种，全部预处理出来贪心拆，于是查询复杂度就是 $O(\alpha(n))$ 的了。

于是我们得到了一个 $O(n\alpha(n))-O(\alpha(n))$ 的算法。但不难注意到这个东西的空间和预处理都不是很牛，于是我们在底层悄咪咪套一层 $O(\alpha(n))$ 的分块，然后就变成 $O(n)-O(\alpha(n))$ 了。做完。

这里挂个板子吧。应该很清楚：预处理阿克曼和前缀拆分，建线段树和结构，查询。两个小细节：我们其实在代码里并不需要处理三维阿克曼的值，只算 $c=1$ 即可；我们可以在算阿克曼函数的时候进行上界截断，反正这玩意要多大都没意义。

constexpr struct ACK_PRECALCER {
  constexpr static int A = 3, H = 30;
  int Ack[A][H];
  tuple<int, int, int> pos[H][A];
  span<tuple<int, int, int>> pth[H];
  constexpr ACK_PRECALCER() {
    iota(Ack[0], Ack[0] + H, 1);
    for (int i = 1; i < A; ++i)
      for (int j = 0; j < H; ++j)
        for (int T = j + 1, &x = Ack[i][j] = j; T && x < H; --T)
          x = Ack[i - 1][x];
    for (int j = 1; j < H; ++j) {
      int i = 1, x = A - 1, t = 0;
      while (i < j) {
        while (Ack[x][i] > j) --x;
        int k = i - 1, c = -1;
        while (Ack[x][i] <= j) i = Ack[x][i], ++c;
        pos[j][t++] = {k, x, c};
      }
      pth[j] = span(pos[j], t);
    }
  }
} Ack;
template <class S, auto op, auto e>
  requires is_convertible_v<decltype(op), function<S(S, S)>> &&
           is_convertible_v<decltype(e), function<S()>>
class uttree {
  constexpr static int A = ACK_PRECALCER::A, B = (A + 1) << 1;
  typedef pair<S, S> S_p;
  static S_p op_p(S_p x, S_p y) {
    return {op(x.first, y.first), op(y.second, x.second)};
  }
  vector<S> val, pre, suf;
  vector<array<vector<S_p>, A>> tog;

 public:
  void build(const vector<S>& v) {
    int n = v.size();
    val = pre = suf = v;
    for (int i = 1; i < n; ++i)
      if (i % B) pre[i] = op(pre[i - 1], pre[i]);
    for (int i = n - 1; i; --i)
      if (i % B) suf[i - 1] = op(suf[i - 1], suf[i]);
    if (n <= (B << 1)) return;
    int N = (n - 1) / B, H = __lg(N) + 1, M = 1 << H++;
    vector<S> zkw(M << 1, e());
    for (int i = 1, j = B; i < N; ++i, j += B)
      zkw[i | M] = accumulate(val.data() + j, val.data() + j + B, e(), op);
    for (int i = M - 1; i; --i) zkw[i] = op(zkw[i << 1], zkw[i << 1 | 1]);
    tog.resize(M << 1);
    for (int h = H - 2, s = 4; s <= M; s <<= 1, --h)
      for (int x = s; x < (s << 1); ++x)
        for (int i = 0; i < A; ++i)
          for (int y = h, c = 0; (y = Ack.Ack[i][y]) < H && c < h; ++c)
            tog[x][i].push_back(
                c ? op_p(tog[x][i][0], tog[x >> (Ack.Ack[i][h] - h)][i][c - 1])
                : i     ? op_p(tog[x][i - 1][0],
                               tog[x >> (Ack.Ack[i - 1][h] - h)][i - 1][h - 1])
                : x & 1 ? pair{e(), zkw[x ^ 1]}
                        : pair{zkw[x ^ 1], e()});
  }
  S query(int l, int r) const {
    if (l / B >= --r / B)
      return accumulate(val.data() + l, val.data() + r + 1, e(), op);
    S L = suf[l], R = pre[r];
    if (int M = tog.size() >> 1; (l = l / B | M) + 1 < (r = r / B | M))
      for (auto [j, x, y] : Ack.pth[__lg(l ^ r) + 1])
        L = op(L, tog[l >> j][x][y].first), R = op(tog[r >> j][x][y].second, R);
    return op(L, R);
  }
  uttree() {}
  explicit uttree(const vector<S>& v) { build(v); }
};

可以用 GBST 或树剖上树，懒得搞了。对高度的定义略加修改可以把 $\alpha$ 搞成双参，同懒。

以上。