Rotate and Flip

题目描述

平面上有 $N$ 个棋子。棋子 $i$ 的坐标为 $(X_i,Y_i)$。可能存在多个棋子位于相同坐标。 我们将依次进行 $M$ 次操作 $\mathrm{op}_1, \ldots, \mathrm{op}_M$。有四类操作，下面描述它们以及输入格式。

$1$：将每个棋子绕原点顺时针旋转 $90$ 度； $2$：将每个棋子绕原点逆时针旋转 $90$ 度； $3 p$：将每个棋子关于直线 $x=p$ 对称移动； $4 p$：将每个棋子关于直线 $y=p$ 对称移动。

给出 $Q$ 个查询。在第 $i$ 个查询中，给定两个整数 $A_i$ 和 $B_i$，请输出在第 $A_i$ 次操作刚执行完之后，棋子 $B_i$ 的坐标。这里，认为在第 $1$ 次操作刚开始之前的时刻等同于“第 $0$ 次操作刚执行完”的时刻。

输入格式

输入从标准输入按以下格式给出： $N$ $X_1$ $Y_1$ $\vdots$ $X_N$ $Y_N$ $M$ $\mathrm{op}_1$ $\vdots$ $\mathrm{op}_M$ $Q$ $A_1$ $B_1$ $\vdots$ $A_Q$ $B_Q$

输出格式

对每个查询的答案各自占一行打印：先输出 $x$ 坐标再输出 $y$ 坐标，两者之间用空格分隔。

1
1 2
4
1
3 3
2
4 2
5
0 1
1 1
2 1
3 1
4 1

1 2
2 -1
4 -1
1 4
1 0

2
1000000000 0
0 1000000000
4
3 -1000000000
4 -1000000000
3 1000000000
4 1000000000
2
4 1
4 2

5000000000 4000000000
4000000000 5000000000

提示

输入中的所有数值均为整数。 $1 \leq N \leq 2\times 10^5$ $1 \leq M \leq 2\times 10^5$ $1 \leq Q \leq 2\times 10^5$ $-10^9 \leq X_i,Y_i \leq 10^9$ $\mathrm{op}_i$ 的格式为上述四种操作之一。 对于形式为 $3 p$ 或 $4 p$ 的操作，$-10^9 \leq p \leq 10^9$。 $0 \leq A_i \leq M$ $1 \leq B_i \leq N$起初，唯一的棋子——棋子 $1$——位于 $(1, 2)$。每次操作将棋子按如下方式移动：$(1,2)\to(2,-1)\to(4,-1)\to(1,4)\to(1,0)$.

标签: AtCoder|abc189E

来源

AtCoder|abc189E