题解：P13914 [CSPro 26] PS 无限版
MrPython
·
·
题解
五种操作都是仿射变换。如果我们能维护一个区间内所有 x,y,x^2,y^2 的和，我们就能轻松回答第六和第七种操作。把仿射变换矩阵写出来：
\begin{bmatrix}
x'\\
y'\\
1
\end{bmatrix}
=
\begin{bmatrix}
a & b & c\\
d & e & f\\
0 & 0 & 1
\end{bmatrix}\begin{bmatrix}
x\\
y\\
1
\end{bmatrix}
展开后可以得到：
\left\{\begin{matrix}
x'= ax + by + c \\
y'= dx + ey + f
\end{matrix}\right.
遇到区间操作，考虑扔到线段树上去维护。懒标记线段树需要分析三点：节点和节点合并、标记和标记合并、节点和标记合并。节点信息维护 \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 上：
\begin{bmatrix}
V_a & V_b & V_c\\
V_d & V_e & V_f\\
0 & 0 & 1
\end{bmatrix}
\begin{bmatrix}
U_a & U_b & U_c\\
U_d & U_e & U_f\\
0 & 0 & 1
\end{bmatrix}
=
\begin{bmatrix}
U_a V_a + U_d V_b & U_b V_a + U_e V_b & U_c V_a + U_f V_b + V_c\\
U_a V_d + U_d V_e & U_b V_d + U_e V_e & U_c V_d + U_f V_e + V_f\\
0 & 0 & 1
\end{bmatrix}
最后考虑如何合并信息与标记。
\left\{\begin{matrix}
\sum_{i=1}^n x_i' &=& \sum_{i=1}^n\left(ax_i+by_i+c\right) = a\sum_{i=1}^n x_i + b\sum_{i=1}^n y_i + cn \\
\sum_{i=1}^n y_i' &=& \sum_{i=1}^n\left(dx_i+ey_i+c\right) = d\sum_{i=1}^n x_i + e\sum_{i=1}^n y_i + fn \\
\sum_{i=1}^n x_i'^2 &=& \sum_{i=1}^n \left(ax_i+by_i+c\right)^2=\sum_{i=1}^n \left(a^2x_i^2+b^2y_i^2+c^2+2abx_iy_i+2acx_i+2bcy_i\right) \\
&=& a^2\sum_{i=1}^n x_i^2 + b^2 \sum_{i=1}^n y_i^2 + c^2n + 2ab \sum_{i=1}^nx_iy_i + 2ac\sum_{i=1}^n x_i + 2bc \sum_{i=1}^n y_i \\
\sum_{i=1}^n y_i'^2 &=& \sum_{i=1}^n \left(dx_i+ey_i+f\right)^2=\sum_{i=1}^n \left(d^2x_i^2+e^2y_i^2+c^2+2dex_iy_i+2dfx_i+2efy_i\right) \\
&=& d^2\sum_{i=1}^n x_i^2 + e^2 \sum_{i=1}^n y_i^2 + f^2n + 2de \sum_{i=1}^nx_iy_i + 2df\sum_{i=1}^n x_i + 2ef \sum_{i=1}^n y_i \\
\sum_{i=1}^n x_iy_i &=& \sum_{i=1}^n\left(ax_i+by_i+c\right)\left(dx_i+ey_i+f\right) \\
&=&\sum_{i=1}^n\left(adx_i^2+bey_i^2+cf+\left(ae+bd\right)x_iy_i+\left(af+cd\right)x_i+\left(bf+ce\right)y_i\right) \\
&=&ad\sum_{i=1}^n x_i^2 +be\sum_{i=1}^n y_i^2+cfn+\left(ae+bd\right)\sum_{i=1}^nx_iy_i+\left(af+cd\right)\sum_{i=1}^n x_i+\left(bf+ce\right)\sum_{i=1}^n y_i
\end{matrix}\right.
数据结构部分也就做完了。再讨论一下五种操作。注意以下矩阵都是左乘的，需要从右往左读。你也不需要实际计算出这些结果，按照顺序在线段树上依次操作即可。
平移：设变换矩阵为 A。由
\left\{\begin{matrix}
x'=x + a \\
y'=b + b
\end{matrix}\right.
可知 A_a=1,A_b=0,A_c=a,A_d=0,A_e=1,A_f=b。因此
A=\begin{bmatrix}
1 & 0 & a\\
0 & 1 & b\\
0 & 0 & 1
\end{bmatrix}
绕点旋转：平移两点，使得旋转中心与原点重合。此时绕原点旋转，是线性变换。再平移回去即可。
\begin{bmatrix}
1 & 0 & a\\
0 & 1 & b\\
0 & 0 & 1
\end{bmatrix}
\begin{bmatrix}
\cos\theta & -\sin\theta & 0\\
\sin\theta & \cos\theta & 0\\
0 & 0 & 1
\end{bmatrix}
\begin{bmatrix}
1 & 0 & -a\\
0 & 1 & -b\\
0 & 0 & 1
\end{bmatrix}
以点为中心缩放：同理，转化为按原点为中心缩放的线性变化问题。
\begin{bmatrix}
1 & 0 & a\\
0 & 1 & b\\
0 & 0 & 1
\end{bmatrix}
\begin{bmatrix}
\lambda & 0 & 0\\
0 & \lambda & 0\\
0 & 0 & 1
\end{bmatrix}
\begin{bmatrix}
1 & 0 & -a\\
0 & 1 & -b\\
0 & 0 & 1
\end{bmatrix}
轴对称：向下平移 b，再绕原点顺时针旋转 \theta，此时对称轴变为 x 轴，y 坐标乘 -1 即可。然后再倒腾回去。
\begin{bmatrix}
1 & 0 & 0\\
0 & 1 & y_0\\
0 & 0 & 1
\end{bmatrix}
\begin{bmatrix}
\cos\theta & -\sin\theta & 0\\
\sin\theta & \cos\theta & 0\\
0 & 0 & 1
\end{bmatrix}
\begin{bmatrix}
1 & 0 & 0\\
0 & -1 & 0\\
0 & 0 & 1
\end{bmatrix}
\begin{bmatrix}
\cos\left(-\theta\right) & -\sin\left(-\theta\right) & 0\\
\sin\left(-\theta\right) & \cos\left(-\theta\right) & 0\\
0 & 0 & 1
\end{bmatrix}
\begin{bmatrix}
1 & 0 & 0\\
0 & 1 & -y_0\\
0 & 0 & 1
\end{bmatrix}
投影：同理，转化为投影到 x 轴，y 坐标乘 0 即可。再倒腾回去。
\begin{bmatrix}
1 & 0 & 0\\
0 & 1 & y_0\\
0 & 0 & 1
\end{bmatrix}
\begin{bmatrix}
\cos\theta & -\sin\theta & 0\\
\sin\theta & \cos\theta & 0\\
0 & 0 & 1
\end{bmatrix}
\begin{bmatrix}
1 & 0 & 0\\
0 & 0 & 0\\
0 & 0 & 1
\end{bmatrix}
\begin{bmatrix}
\cos\left(-\theta\right) & -\sin\left(-\theta\right) & 0\\
\sin\left(-\theta\right) & \cos\left(-\theta\right) & 0\\
0 & 0 & 1
\end{bmatrix}
\begin{bmatrix}
1 & 0 & 0\\
0 & 1 & -y_0\\
0 & 0 & 1
\end{bmatrix}
还有两种询问。
询问 6：输出 \frac{1}{m} \sum_{i=1}^m x_i 与 \frac{1}{m} \sum_{i=1}^m y_i。
询问 7：输出
\sum_{i=1}^m \left(\left(x_i-a\right)^2+\left(y_i-b\right)^2\right)=\sum_{i=1}^m \left(x_i^2-2x_ia+a^2+y_i^2-2y_ib+b^2\right) \\
=\sum_{i=1}^m x_i^2-2a\sum_{i=1}^m x_i+ma^2+\sum_{i=1}^m y_i^2-2b\sum_{i=1}^m y_i+mb^2