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

H_Kaguya

2024-11-16 19:20:54

Solution

猫树!

简单来讲,猫树就是,在普通线段树的基础上,每个节点预处理 \forall i \in [l, mid), [i, mid]\forall i \in (mid, r], [mid + 1, i] 的答案。
这样处理询问 [L, R] 的时候只需要找到满足 l \le L, r \ge R, mid \in [L, R] 的节点,左右 O(1) 合并即可。
预处理复杂度 T(n) = 2T(\frac{n}{2}) + O(n) = O(n \log n)

常规的猫树是 O(n \log n) 预处理 O(1) 查询的。
所以类似四毛子,先按照块长 B = O(\log n) 分块,块间建立猫树,块内预处理前缀和后缀和,然后块内再建猫树。

[提交记录1](https://www.luogu.com.cn/record/186909275) [提交记录2](https://www.luogu.com.cn/record/186911293) 但实际情况是这个东西都没有 ST 表快...... $O(\log n)$ 查询的 ST 表...... [提交记录](https://www.luogu.com.cn/record/186875870) 所以我们把散块的猫树扬了。 块间维护猫树,块内查询直接暴力。 更短了,也更快了。 [提交记录](https://www.luogu.com.cn/record/186912265) 只贴核心代码。 ```cpp constexpr int N = 1 << 20 | 5; int n, m, p; mat frt[N], bak[N]; mat a[N]; mat b[16][(N >> 5) + 1]; void init(); void geta(int, int); signed main() { scanf ("%d%d", &n, &m); p = 1 << __lg(n) + 1; p = max(p, 32); rnd.init(); out.init(); init(); for (int l, r; m; --m) { rnd.genqry(l, r, n); geta(l, r); } printf ("%d\n", out.ans); return 0; } void init() { for (int i = 1; i <= n; ++i) rnd.genmat(a[i]); for (int i = 0; i < p; i += 32) { frt[i] = a[i]; for (int j = 1; j < 32; ++j) frt[i | j] = mul(frt[i | j - 1], a[i | j]); bak[i | 31] = a[i | 31]; for (int j = 30; j >= 0; --j) bak[i | j] = mul(a[i | j], bak[i | j + 1]); } for (int i = 0; i < p; i += 32) b[0][i >> 5] = bak[i]; for (int i = 1; (1 << i) <= (p >> 5); ++i) { for (int j = 0; j < (p >> 5); ) { int k = j + (1 << i - 1), s = j + (1 << i); b[i][k] = b[0][k]; for (int h = k + 1; h < s; ++h) b[i][h] = mul(b[i][h - 1], b[0][h]); b[i][k - 1] = b[0][k - 1]; for (int h = k - 2; h >= j; --h) b[i][h] = mul(b[0][h], b[i][h + 1]); j = s; } } } void geta(int l, int r) { if ((l >> 5) == (r >> 5)) { mat tmp = a[l]; for (int i = l + 1; i <= r; ++i) tmp = mul(tmp, a[i]); out.ot(tmp); return; } mat tmp1 = bak[l], tmp2 = frt[r]; l = (l >> 5) + 1; r = (r >> 5) - 1; if (l == r) tmp1 = mul(tmp1, b[0][l]); else if (l < r) { int bit = __lg(l ^ r) + 1; tmp1 = mul(tmp1, mul(b[bit][l], b[bit][r])); } out.ot(mul(tmp1, tmp2)); } ```