归约矩乘学习笔记

归约矩乘好啊,这样就能第一时间知道谁是嘴巴怪了((

其实主要是自己出题的时候可以随时用很高大上的语言毙掉别人的 idea

学习自 https://www.luogu.com.cn/blog/Ynoi/qian-tan-gui-yue-ju-cheng ,树剖姐姐 /se

说人话就是把某个问题转化成矩阵乘法,以此来证明它的复杂度不低于多少多少的一个东西,如果你经常做 Ynoi 那你分析理论最低复杂度的时候可能会用到

当然你也可以利用这玩意儿提出一个 polylog 的区间逆序对然后去捧一个图灵奖,这我拦不住你

本文全部假设 $n, q$ 同阶


1、给你一棵树,问一条链上颜色数

第一眼看下来,这玩意儿和矩乘似乎没有任何关系

没有关系也要给他构造出关系来

我们假设有两个 $\sqrt{\frac n 2} \times \sqrt{\frac n 2}$ 的01矩阵 $A, B$ ,我们要对这两个东西做矩阵乘法

然后我们构造一棵树,我们考虑取一个根,挂下来 $2\sqrt{\frac n 2}$ 条链,每条链长度 $\sqrt{\frac n 2}$

发现我们矩阵乘法的结果 $C$ ,应该要满足 $C_{i,j}=\sum_{k}[A_{i,k}=1][B_{k,j}=1]$

考虑这东西建立联系的方法,我们把所有链分为两部分,然后对于 $A_{i,k}=1$ 的,我们在第一部分的第 $i$ 条链上挂一个颜色为 $k$ 的结点,同理,对于 $B_{k,j}=1$ 的,我们在第二部分的第 $j$ 条链上挂一个颜色为 $k$ 的结点

剩下的结点与根结点同色就可以当做无色处理

然后我们考虑一个 $C_{i,j}$ 怎么求

我们发现,如果我们对 $i, j$ 这两条链进行询问,那么只要能让每一个同时在 $i, j$ 上出现过的 $k$ 都会产生 $1$ 的贡献,就可以通过 $O(n)$ 次询问求出 $C$

我们发现对 $i,j$ 数颜色的话,贡献可以拆成是 “$i$ 上颜色数 + $j$ 上颜色数 - $i, j$ 公有颜色数 + 根的颜色”

前两部分我们都可以在预处理的时候 $O(n)$ 一起求,甚至于我们发现我们把矩阵转化为树的时候可以直接考虑贡献

甚至于可以把没有颜色的点看成不存在,然后把这两段数颜色理解成链长度,显然是可以 $O(n)$ 预处理 $O(1)$ 求的

那么通过移项就可以轻易解出后面这一部分,因此我们链上数颜色的复杂度如果是 $O(nx)$ 的话(即单次是 $O(x)$),那么我们就可以在 $O(nx)$ 的时间内完成一个 $\sqrt{\frac n 2} \times \sqrt{\frac n 2}$ 的矩阵乘法

因此这个问题不弱于 $\sqrt{\frac n 2} \times \sqrt{\frac n 2}$ 的矩阵乘法


2、给一个序列,假设每个颜色贡献为颜色出现次数的平方,求区间贡献和

我们考虑上面那道题是怎么归约的:

分成 $O(\sqrt{n})$ 份,构造矩乘与问题的关系,然后把询问转化成矩乘的单点询问

考虑这是序列问题,因此我们对序列分块,分成 $\sqrt{n}$ 块大小为 $\sqrt{n}$ 的

考虑构造一个 $O(\sqrt{n}) \times O(\sqrt{n})$ 的矩阵乘法 $C=A\times B$, $A, B$ 还是01矩阵

然后说一句废话 $C_{i,j}=\sum_{k}[A_{i,k}=1][B_{k,j}=1]$

考虑还是分两部分,然后传统艺能对于 $A_{i,k}=1$ 的,我们在第一部分的第 $i$ 个块上塞一个颜色为 $k$ 的结点,同理,对于 $B_{k,j}=1$ 的,我们在第二部分的第 $j$ 个块上塞一个颜色为 $k$ 的结点

考虑对于一次第 $l$ 个块到第 $r$ 个块的查询,我们假设答案是 $f(l,r)$

然后我们考虑 $f(l - 1, r + 1)$ 与 $f(l, r)$ 的区别,在于 $l-1$ 到 $[l, r]$ 的贡献,以及 $r + 1$ 到 $[l, r]$ 的贡献,还有 $l-1, r+1$ 两个块间的贡献

发现最后一部分就是我们要求的

而前两部分可以通过 $f(l-1, r)-f(l, r)$ 与 $f(l, r + 1)-f(l, r)$ 的容斥算出来

考虑我们这样的话还是 $O(n)$ 次询问可以得出 $C$ 矩阵,因此这个问题是不弱于 $O(\sqrt{n}) \times O(\sqrt{n})$ 的矩乘的


3、区间逆序对

我们先求一个区间逆序对,再用相同的复杂度求一个区间顺序对,简单容斥下,大家看看剩下的是什么?

哒哒哒

其实就是上一题((


4、区间加区间 rank

其实就是 $\le k$ 的数的个数

还是传统艺能 $C=A\times B$

说句废话 $C_{i,j}=\sum_{k}[A_{i,k}=1][B_{k,j}=1]$

发现不太好一通构造之后 $O(n)$ 次查询了,怎么办?

我们考虑利用修改的性质,边修改边查询

因此这次我们不把序列分块分两部分,我们通过一部分查询一部分修改来区分 $A, B$

我们考虑若 $B_{k,j}=1$ ,我们在块 $k$ 塞一个 $j$

然后我们枚举 $i$ ,然后对于 $A_{i, k}=1$ 的块 $k$ 我们加上一个相同的极大数 $x$

这里我们可以通过一些手段使得每一层独立,这样子的话我们可以只对于一层分析

那么对于这一层,我们相当于问出 $x+j$ 的个数,就能得到 $C_{i,j}$ 了,可以理解为 $+x$ 的操作满足了 $A_{i,k}=1$ ,$j$ 满足了 $B_{k,j}=1$

这个可以用差分配合区间 rank 很快求出,然后发现修改查询都是 $O(n)$ 的

因此这道题不弱于 $O(\sqrt{n})\times O(\sqrt{n})$ 的矩阵乘法


5、区间众数出现次数

懒得更洛谷的了

感谢叉姐友情赠送的论文链接 https://cs.au.dk/~larsen/papers/linear_mode.pdf

考虑建立矩阵乘法 $C=A\times B$ ,但是这里特殊一些,我们让 $C_{i,j}=\text{or}_{k} [A_{i,k}=1][B_{k,j}=1]$ 即把原先的加法换成或运算

然后考虑构造若干个可重集 $S_i, T_j$ 其中 $S_i=\{k|A_{i,k}=1\},T_i=\{k|B_{k,j}=1\}$

那么就有 $C_{i,j}=[S_i \cap T_j \neq \emptyset]$

然后我们考虑把这两个集合合并成一个 可重集 ,发现对这个可重集跑众数出现次数之后,如果答案是 $2$ 那么这两个集合就有交,答案为 $1$ 则没有交

那么我们传统艺能分块然后分成两部分,不过显然整块查询已经不能满足我们了

我们考虑对于前一部分的每一个块,左边 $\sqrt{n}-|A_i|$ 个数塞 $[1, \sqrt{n}]-A_i$ ,剩下的塞 $A_i$ ,这两部分内部顺序任意,另一边同理,不过是右边塞 $[1, \sqrt{n}] - B_j$,而左边塞 $B_j$

这样子的话,我们每一次假设要查询 $A_i, B_j$ ,我们就找到相对应的两个块然后直接查就行,注意这里对应的区间要留两边的散块,使其分别恰好包含 $A_i, B_j$ 中的所有元素,发现按照上面的构造这是可以做到的

这样的话中间的整块全部都是 $[1, \sqrt{n}]$ ,因此直接减掉就行

那么剩下的判一下 $1, 2$ 即可

由此得到区间众数出现次数不弱于 $O(\sqrt{n}) \times O(\sqrt{n})$ 的布尔矩阵乘法


6、给一个序列,假设每个颜色贡献为颜色出现次数的平方,求区间贡献和

梅开二度

之前分析了这玩意儿不弱于 $O(\sqrt{n})\times O(\sqrt{n})$ 的矩阵乘法,但我没说这玩意儿就是一只根号的啊

毕竟矩阵乘法也可以比 $O(n^3)$ 更快啊

那么这次我们反向归约,用矩阵乘法实现这个东西

首先根号分治,按出现次数排序取前 $K$ 大

那么剩下的部分出现次数一定不大于 $\frac{n}{K}$ ,考虑可以转化为二维数点,实现精细可以做到 $O(\frac{n^2}{K})$

然后另一部分,首先离散化,然后考虑按 $k$ 为 块数 分块,然后得到两个矩阵 $A,B$ ,其中 $A_{i,k}$ 表示第 $i$ 个块中 $k$ 的出现次数, $B_{k,j}$ 表示第 $j$ 个块中 $k$ 的出现次数

那么求 $C=A \times B$ 就得到了任意两个块之间的贡献,然后可以二维前缀和处理,发现这部分复杂度就是矩阵乘法的复杂度

暂时不会,咕了