4200: Loong Tracking

# Loong Tracking ### 内存 1024MB ### 时间 2S ## 题目描述 小高创建了一个游戏，玩家在坐标平面上控制一条龙。龙由$N$个部分组成，编号从$1$到$N$，其中第$1$部分被称为"头"。初始时，第$i$部分位于坐标$(i,0)$。按以下方式处理$Q$个查询： 1. `1 C`：将头部向$C$方向移动$1$个单位。这里，$C$是$R$、$L$、$U$和$D$之一，分别表示$x$轴正方向、$x$轴负方向、$y$轴正方向和$y$轴负方向。除头部外的每个部分都会跟随前面的部分移动。也就是说，第$i$部分$(2≤i≤N)$会移动到第$i-1$部分移动前所在的坐标。 2. `2 p`：查询第$p$部分的坐标。 ## 输入格式 输入从标准输入中给出，格式如下： $N$ $Q$ $query_1$ $\vdots$ $query_Q$ 每个查询是以下两种格式之一： $1\ C$ $2\ p$ ## 输出格式 输出$q$行，其中$q$是第二种查询的数量。第i行应包含用空格分隔的$x$和$y$，其中$(x,y)$是第$i$个此类查询的答案。 ## 输入输出样例 ### 输入样例1 ``` 5 9 2 3 1 U 2 3 1 R 1 D 2 3 1 L 2 1 2 5 ``` ### 输出样例1 ``` 3 0 2 0 1 1 1 0 1 0 ``` ## 数据范围与提示 【样例1说明】 在处理第二种查询时，各部分的位置如下：  注意，多个部分可能存在于同一坐标。 【数据范围】 $2 ≤ N ≤ 10^6$ $1 ≤ Q ≤ 2×10^5$ 对于第一种查询，$C$是$R$、$L$、$U$和$D$之一。 对于第二种查询，$1 ≤ p ≤ N$，所有输入的数值都是整数。 ## 题目来源 ABC335C