猫树!
简单来讲,猫树就是,在普通线段树的基础上,每个节点预处理 \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));
}
```