P8105

STA_Morlin · 2023-02-27 15:19:18 · 题解

考虑用矩阵描述区间操作，线段树维护。

对于点 (x,y)，表为行向量 \begin{bmatrix}x&y\end{bmatrix}，则：

• 平移：\begin{bmatrix}x'&y'\end{bmatrix}=\begin{bmatrix}x&y\end{bmatrix}+\begin{bmatrix}a&b\end{bmatrix}。
• 旋转：不妨设关于 (0,0) 旋转（不满足形式可以先平移过去），\begin{bmatrix}x'&y'\end{bmatrix}=\begin{bmatrix}x&y\end{bmatrix}\begin{bmatrix}\cos g^{\circ}&\sin g^{\circ}\\-\sin g^{\circ}&\cos g^{\circ}\end{bmatrix}。
• 位似：不妨设关于 (0,0) 位似（不满足形式可以先平移过去），\begin{bmatrix}x'&y'\end{bmatrix}=\begin{bmatrix}x&y\end{bmatrix}\begin{bmatrix}0&\frac pq\\\frac pq&0\end{bmatrix}。

区间查询只需要求区间的向量和即可，相当于区间加区间乘区间求和，这就是线段树 2。于是问题被 \Theta(q\log n) 解决。

然而如果直接写常数比较大可能需要展开矩阵乘法去掉一些没用的操作这样就能过了。