自动搬运

查看原文

来自洛谷，原作者为

	wangbinfeng 今天搞完大概就永远不会碰 OI 了，大家祝好！

搬运于2025-08-24 22:48:18，当前版本为作者最后更新于2023-06-25 13:54:11，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

容易想到暴力思路，就不详细说明。

观察数据范围（$1\leqslant n\leqslant 10^5$，$1\leqslant m\leqslant 5\times10^5$），发现暴力的时间复杂度为 $O(nm)$，显然无法通过本题。

继续分析易得，时间复杂度过大主要由操作1造成。因此考虑提高操作1（修改所有军队）的速度。

考虑引入两个新变量 $m_x,m_y$ 记录总偏移量。每次执行操作1时，$m_x=m_x+p,m_y=m_y+q$，而执行操作3时输出 $x_i+m_x,y_i+m_y$（可以发现将操作一的时间复杂度由 $O(n)$ 降至 $O(1)$）。

操作2要求交换单个军队的横纵坐标，修改时应先将原坐标 $x_i,y_i$ 分别加偏移量 $m_x,m_y$ 求出现在坐标，再将现在坐标的 $x,y$ 交换。不要忘记交换完需要再减掉偏移量。

最终时间复杂度：$O(n+m)$。

代码：

#include<bits/stdc++.h>
using namespace std;
long long mx,my,n,m;
inline int read(){
    char c;
    int ret=0,f=1;
    for(c=getchar();c<'0'||c>'9';c=getchar())if(c=='-')f=-f;
    for(;c>='0'&&c<='9';c=getchar())ret=ret*10+c-'0';
    return ret*f;
}                                               //快读模板（本题读入数据有点多，快读可以加速）
class NODE{                                     //军队类
public:                                         //类中元素默认私有，需改变为公有（结构体不需要这句）
	int x,y;                                    //坐标
	void swap(){
		int t=x+mx-my;
		x=y+my-mx;
		y=t;
	}                                           //交换横纵坐标
	void print(){printf("%d %d\n",x+mx,y+my);}  //输出
}node[100009];
int main() {
	n=read(),m=read();
	for(int i=1;i<=n;i++)node[i].x=read(),node[i].y=read();
	while(m--)
		switch(read()){
			case 1:                             //操作一
				mx+=read(),my+=read();          //修改偏移量
				break;                          //勿忘
			case 2:                             //操作二
				node[read()].swap();            //交换横纵坐标（调用类中的函数）
				break;                          //勿忘
			case 3:                             //操作三
				node[read()].print();           //输出横纵坐标
		}
}