#P3542. DZY Loves March
DZY Loves March
DZY Loves March
题目描述
一块 的方形区域内驻有 支军队,编号为 到 。第 支军队的驻地为 。多支军队可驻扎在同一位置。
依次发生 个事件。事件要么将一支军队的驻地沿指定方向移动 个单位,要么由一支军队发起集结。发起集结的军队编号为 。在本次给定的编号范围 中,所有与它在同一行或同一列的军队都要赶到它的驻地。从军队 的驻地赶到军队 的驻地,花费为
求每次集结的花费总和对 取模后的结果。同一支军队至多计一次,集结结束后所有参与军队回到各自的原驻地。
输入格式
第一行两个整数 。接下来 行,第 行的两个整数 表示军队 的初始驻地。
接下来一行是整数 ,随后 行,每行给出一个事件。
S x' d表示移动。方向S为U、D、L、R,分别使 增加、 减少、 减少、 增加 。Q x' l r表示一次集结,编号范围为 。
两种事件的实际军队编号均为 ,其中 为按位异或。 是最近一次已输出的答案,初始为 。移动事件不改变 。其他参数直接使用输入值。
输出格式
每次集结输出一行整数,表示该次集结的总花费对 取模后的结果。
样例 #1
5 3
1 2
2 2
3 2
2 1
2 3
7
Q 2 1 5
Q 6 3 4
D 1 1
Q 0 1 5
Q 7 1 5
L 5 1
Q 4 1 5
4
2
3
6
4
依次使用前一次输出解码后,七个事件为
Q 2 1 5
Q 2 3 4
D 3 1
Q 2 1 5
Q 4 1 5
L 3 1
Q 2 1 5
下图从左到右依次是初始驻地、第三个事件移动后和第六个事件移动后的位置。

数据范围
,,,。军队移动不会离开给定区域。