自动搬运

查看原文

来自洛谷，原作者为

	STA_Morlin 命运可以被相信，但不能被期待。

搬运于2025-08-24 22:36:01，当前版本为作者最后更新于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)$ 解决。

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