感觉这个操作像是线性变换啊,可能可以线段树维护一下矩阵乘法
by dreagonm @ 2019-06-25 08:34:53
@[tuxiaobei](/space/show?uid=148050)
不是很清楚您的意思。不过如果一个数据结构吃力,看看用两个行不行,互相维护。或者使用数学方法将难维护的化成几个容易维护的再在数据结构外面用数学方法计算一下。
by Haishu @ 2019-06-25 08:38:31
@[tuxiaobei](/space/show?uid=148050)
~~比如您可以考虑可持久化~~
by Haishu @ 2019-06-25 08:45:47
线段树维护矩阵乘法
by iostream @ 2019-06-25 09:07:59
@[iostream](/space/show?uid=13052) 支持
by wh_ZH @ 2019-06-25 09:29:43
每个叶子维护一个矩阵 $\begin{bmatrix} a \\ b\end{bmatrix}$ 。若修改操作是 $a=a \cdot x, b = b+a \cdot y$ ,由于:
$$\begin{bmatrix} a & b \end{bmatrix} \times \begin{bmatrix} x & y \\ 0 & 1\end{bmatrix} = \begin{bmatrix} ax & b+ay \end{bmatrix}$$
你只需要把这个区间中的每个矩阵乘上第二个即可。用线段树打个标记即可。合并时维护你想要的信息。
by Gypsophila @ 2019-06-25 10:02:27
@[tuxiaobei](/space/show?uid=148050)
by Gypsophila @ 2019-06-25 10:02:34