【题解】P9430 [NAPC-#1] Stage2 - Darkness

· · 题解

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

观察数据范围（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();           //输出横纵坐标
        }
}