题解：P13914 [CSPro 26] PS 无限版

五种操作都是仿射变换。如果我们能维护一个区间内所有 $x,y,x^2,y^2$ 的和，我们就能轻松回答第六和第七种操作。把仿射变换矩阵写出来：

展开后可以得到：

遇到区间操作，考虑扔到线段树上去维护。懒标记线段树需要分析三点：节点和节点合并、标记和标记合并、节点和标记合并。节点信息维护 $\sum_{i=1}^n x_i,\sum_{i=1}^n y_i, \sum_{i=1}^n x_i^2, \sum_{i=1}^n y_i^2, \sum_{i=1}^n x_i y_i$。懒标记维护仿射变换矩阵中的 $a,b,c,d,e,f$，其幺元即为对角矩阵（$a=1,b=0,c=0,d=0,e=1,f=0$）。

节点和节点用脚合并，直接加起来就行。

标记和标记合并即将两个矩阵相乘。注意我使用的列矩阵，所以后来的标记 $V$ 应该左乘到矩阵 $U$ 上：

最后考虑如何合并信息与标记。

数据结构部分也就做完了。再讨论一下五种操作。注意以下矩阵都是左乘的，需要从右往左读。你也不需要实际计算出这些结果，按照顺序在线段树上依次操作即可。

平移：设变换矩阵为 $A$。由

可知 $A_a=1,A_b=0,A_c=a,A_d=0,A_e=1,A_f=b$。因此

绕点旋转：平移两点，使得旋转中心与原点重合。此时绕原点旋转，是线性变换。再平移回去即可。

以点为中心缩放：同理，转化为按原点为中心缩放的线性变化问题。

轴对称：向下平移 $b$，再绕原点顺时针旋转 $\theta$，此时对称轴变为 $x$ 轴，$y$ 坐标乘 $-1$ 即可。然后再倒腾回去。

投影：同理，转化为投影到 $x$ 轴，$y$ 坐标乘 $0$ 即可。再倒腾回去。

还有两种询问。

询问 6：输出 $\frac{1}{m} \sum_{i=1}^m x_i$ 与 $\frac{1}{m} \sum_{i=1}^m y_i$。

询问 7：输出