#503. 「LibreOJ β Round」ZQC 的课堂

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: mps2000

题目描述

叮铃铃 …… 上课铃响了。

「啊,又是无聊的 math」,坐在教室里的 ZQC 这样想道。Mr.Sam 今天在课上讲了平面直角坐标系上的向量。「这不是幼儿园姿势么」,ZQC 实在忍不住,睡着了。Mr.Sam 把 ZQC 给叫醒,并给了他这样一道题:

假设有一平面直角坐标系,ZQC 有一支画笔,起点是 (1, 1) ,现在有 n 个向量,第 i 个向量形如 (x_i, y_i) ,且满足每一个向量都满足 x_i, y_i 均为偶数。ZQC 按顺序根据这些向量改变自己的画笔的位置,即位置依次改变成 (1 + x_1, 1 + y_1), (1 + x_1 + x_2, 1 + y_1 + y_2) \ldots 。每次改变位置时,画笔都沿两点之间的最短距离移动。结束时,画笔的运动轨迹一定由 n 条线段组成。Mr.Sam 要 ZQC 回答这些线段穿过 x 轴和 y 轴的总次数之和是多少。

但这样的问题对 ZQC 来说太简单了,于是 Mr.Sam 设定了一个指针,一开始指在第一个向量。现在他做了 q(q \leq 3 \times 10 ^ 5) 个操作,操作有四种,分别是:

  1. \texttt{B} 表示把指针向后移动,如果越界则视为无效。即,如果设指针移动前的位置是 i ,那么移动后的位置是 \max(1,i-1)
  2. \texttt{F} 表示把指针向前移动,如果越界则视为无效。即,如果设指针移动前的位置是 i ,那么移动后的位置是 \min(n,i+1)
  3. \texttt{C} ~ \text{nx} ~ \text{ny} 把当前指针所指的向量修改为 (\text{nx},\text{ny}) ,这里同样满足 \text{nx},\text{ny} 为偶数。
  4. \texttt{Q} 假设 ZQC 从起点开始,按第 1 个到第 n(n \leq 10 ^ 5) 个的顺序沿向量走,询问画出的 n 条线段穿过 x 轴和 y 轴次数的总和。

ZQC 想了想,这不是思博题么。

我是要拿图灵奖和菲尔兹奖的男人,这种题浪费我时间,不做!

但是如果不做的话,ZQC 又会遭到 detention,所以他希望聪明的你能在 \texttt{+1s} 内帮他解决这道题。

输入格式

第一行一个正整数 n
接下来 n 行每行两个整数 x, y ,保证 x, y 均为偶数。
接下来一行一个整数 q
接下来 q 行,格式见「题目描述」。

输出格式

对于询问中的每个 q ,输出画出的 n 条线段穿过 x 轴和 y 轴次数的总和。

样例

样例输入

6
2 2
2 -6
-2 -4
-6 4
10 -10
-8 12
16
Q
C -4 -4 
F
F
Q
F
C 6 -2 
B
B
B
Q
C 0 6 
Q
F
C -8 4 
Q

样例输出

4
4
3
1
5

数据范围与提示

题目中出现的坐标值的绝对值均不超过 500

因为起点是 (1,1) 而每个向量的每个分量均为偶数,故每次画笔停留的位置横纵坐标均为奇数,不可能在坐标轴上。