Loong Tracking

题目描述

Takahashi 创建了一个游戏，玩家在坐标平面上控制一条龙。 这条龙由编号为 $1$ 到 $N$ 的 $N$ 个部分组成，编号 $1$ 的部分称为 头部。 最初，第 $i$ 部分位于坐标 $(i,0)$。按如下方式处理 $Q$ 个查询。

$1 C$：将头部沿方向 $C$ 移动 $1$。这里，$C$ 为 $R$、$L$、$U$ 或 $D$ 中的一个，分别表示正 $x$ 方向、负 $x$ 方向、正 $y$ 方向和负 $y$ 方向。除头部外的每个部分都会跟随其前面的部分移动。也就是说，第 $i$ 部分 $(2\leq i \leq N)$ 移动到第 $i-1$ 部分在移动之前所在的坐标。 $2 p$：查询第 $p$ 部分的坐标。

输入格式

输入按照下列格式从标准输入给出： $N$ $Q$ $\mathrm{query}_1$ $\vdots$ $\mathrm{query}_Q$

每个查询为以下两种格式之一： $1$ $C$

$2$ $p$

输出格式

输出 $q$ 行，其中 $q$ 是第二类查询的数量。
第 $i$ 行应包含用空格分隔的 $x$ 和 $y$，其中 $(x,y)$ 是第 $i$ 个此类查询的答案。

5 9
2 3
1 U
2 3
1 R
1 D
2 3
1 L
2 1
2 5

3 0
2 0
1 1
1 0
1 0

提示

$2 \leq N \leq 10^6$ $1 \leq Q \leq 2\times 10^5$ 对于第一类查询，$C$ 为 $R$、$L$、$U$ 或 $D$ 中的一个。 对于第二类查询，$1\leq p \leq N$。 所有数值输入均为整数。在处理每个第二类查询时，各部分处于如下位置： 注意多个部分可能位于相同的坐标。

标签: AtCoder|abc335C

来源

AtCoder|abc335C