CCF CSP 2020-12 T5 星际旅行 （动态开点线段树维护矩阵）

大意：您需要写一个数据结构维护一个三元组数组，支持以下四种操作：

1、区间中的所有三元组的每个分量分别加上a，b，c

2、区间中的所有三元组的每个分量分别乘以k

3、区间中的所有三元组从{x, y, z}旋转为{y, z, x}

4、查询区间中的所有三元组的各分量和的平方再求和

其中1、2、4是线段树基本操作，3则可以通过矩阵乘法进行初等变换来解决。

树上每个节点维护一个这样的矩阵：

分别表示区间x、y、z的和。操作1可以用相同类型矩阵打tag相加。

操作2: 左乘

操作3：左乘

因为矩阵乘法有结合律，所以标记可以合并从而保证单次操作复杂度。但是会带一个的矩阵乘法常数，也可以把加法换成1*3的矩阵稍微优化一下。

还有一种维护方法是维护4*4的齐次矩阵，就可以把加法变成乘法，于是只需要乘法标记，简化掉双标记线段树的麻烦。

恶心的地方：n<=1e9

于是需要动态开点。试了下珂朵莉树，由于没有区间赋值，发现1e4内还可以0.76s，4e4暴涨到86s导致TLE

通过代码：

https://paste.ubuntu.com/p/s5F4vj2w5t/