#P3533. [Sdoi2014]向量集
[Sdoi2014]向量集
[SDOI2014] 向量集
题目描述
维护一个初始为空的向量集合,并按顺序执行以下操作。
A x y加入一个向量 。向量按加入顺序从 开始编号。Q x y l r求编号从 到 的所有已加入向量与 的点积的最大值。
向量 与向量 的点积为 。若当前已经加入 个向量,则查询满足 。
输入格式
第一行给出整数 和字符 ,分别表示操作数和数据类别。接下来 行,每行给出一个操作。
当 时,每个操作的整数参数均经过加密。读入的每个参数 x 需要与上一次查询答案的低 位按位异或。第一次查询之前,上一次查询答案为 。两个查询之间的加入操作不会改变该值。
inline int decode(int x, long long lastans) {
return x ^ (lastans & 0x7fffffff);
}
function decode(x: longint; lastans: int64): longint;
begin
decode := x xor (lastans and $7fffffff);
end;
当 时,直接使用读入的参数。
输出格式
每遇到一次 Q,输出一行整数,表示查询结果。
样例 #1
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–3 | A |
无 | |
| 4 | B |
加入向量的横坐标单调不下降,且每次查询均满足 | |
| 5–6 | C |
加入向量的横坐标单调不下降 | |
| 7 | D |
每次查询均满足 | |
| 8–9 | E |
无 | |
| 10 | F |