#2197. 「SDOI2014」向量集

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

题目描述

维护一个向量集合,在线支持以下操作:

  1. A x y :加入向量 (x, y)
  2. Q x y l r:询问第 L 个到第 R 个加入的向量与向量 (x, y) 的点积的最大值。集合初始时为空。

注:向量 (x, y) (z, w) 的点积定义为 xz+yw

输入格式

输入的第一行包含整数 N 和字符 s ,分别表示操作数和数据类别;
接下来 N 行,每行一个操作,格式如上所述。

请注意 s \neq E 时,输入中的所有整数都经过了加密。你可以使用以下程序得到原始输入:

inline int decode (int x long long lastans) {
     return x ^ (lastans & Ox7fffffff);
}
function decode
begin

其中 x 为程序读入的数,lastans 为之前最后一次询问的答案。在第一次询问之前,lastans =0

输出格式

对每个 Q 操作,输出一个整数表示答案。

样例

样例输入

6 A
A 3 2
Q 1 5 1 1
A 15 14
A 12 9
Q 12 8 12 15
Q 21 18 19 18

样例输出

13
17
17

样例解释

解密之后的输入为

6 E
A 3 2
Q 1 5 1 1
A 2 3
A 1 4
Q 1 5 1 2
Q 4 3 2 3

数据范围与提示

对于所有的数据, 1 \leq N \leq 4 \times 10^5 ,操作中的向量坐标满足 |x|,|y| \leq 10^8 ,询问满足 1 \leq L \leq R \leq T ,其中 T 为已经加入的向量个数。