#P3542. DZY Loves March

    ID: 2752 传统题 1000ms 256MiB 尝试: 236 已通过: 32 难度: 7 上传者: 标签>难度分类提高数据结构Treap模拟与实现技巧增量维护CF2200ByDzy

DZY Loves March

DZY Loves March

题目描述

一块 m×mm\times m 的方形区域内驻有 nn 支军队,编号为 11 到 nn。第 ii 支军队的驻地为 (xi,yi)(x_i,y_i)。多支军队可驻扎在同一位置。

依次发生 tt 个事件。事件要么将一支军队的驻地沿指定方向移动 dd 个单位,要么由一支军队发起集结。发起集结的军队编号为 xx。在本次给定的编号范围 [l,r][l,r] 中,所有与它在同一行或同一列的军队都要赶到它的驻地。从军队 ii 的驻地赶到军队 jj 的驻地,花费为

(xi−xj)2+(yi−yj)2.(x_i-x_j)^2+(y_i-y_j)^2.

求每次集结的花费总和对 109+710^9+7 取模后的结果。同一支军队至多计一次,集结结束后所有参与军队回到各自的原驻地。

输入格式

第一行两个整数 n,mn,m。接下来 nn 行,第 ii 行的两个整数 xi,yix_i,y_i 表示军队 ii 的初始驻地。

接下来一行是整数 tt,随后 tt 行,每行给出一个事件。

  • S x' d 表示移动。方向 S 为 U、D、L、R,分别使 yy 增加、yy 减少、xx 减少、xx 增加 dd。
  • Q x' l r 表示一次集结,编号范围为 [l,r][l,r]。

两种事件的实际军队编号均为 x=x′⊕lastansx=x'\mathbin{\oplus}\mathrm{lastans},其中 ⊕\oplus 为按位异或。lastans\mathrm{lastans} 是最近一次已输出的答案,初始为 00。移动事件不改变 lastans\mathrm{lastans}。其他参数直接使用输入值。

输出格式

每次集结输出一行整数,表示该次集结的总花费对 109+710^9+7 取模后的结果。

样例 #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

下图从左到右依次是初始驻地、第三个事件移动后和第六个事件移动后的位置。

两次移动中,3 号军队先下移一格,再左移一格,最后与 4 号军队同处。

数据范围

1≤n≤1051\le n\le10^5,1≤m≤10181\le m\le10^{18},1≤x≤n1\le x\le n,1≤l≤r≤n1\le l\le r\le n。军队移动不会离开给定区域。