#P3533. [Sdoi2014]向量集

    ID: 2743 传统题 2000ms 512MiB 尝试: 1598 已通过: 372 难度: 8 上传者: 标签>难度分类提高+/省选-数据结构普通线段树计算几何凸包Andrew 算法排序与序列处理双指针合并有序序列二分查找叉积点积CF2500

[Sdoi2014]向量集

[SDOI2014] 向量集

题目描述

维护一个初始为空的向量集合,并按顺序执行以下操作。

  • A x y 加入一个向量 (x,y)(x,y)。向量按加入顺序从 11 开始编号。
  • Q x y l r 求编号从 ll 到 rr 的所有已加入向量与 (x,y)(x,y) 的点积的最大值。

向量 (x,y)(x,y) 与向量 (z,w)(z,w) 的点积为 xz+ywxz+yw。若当前已经加入 TT 个向量,则查询满足 1≤l≤r≤T1\le l\le r\le T。

输入格式

第一行给出整数 NN 和字符 ss,分别表示操作数和数据类别。接下来 NN 行,每行给出一个操作。

当 s≠Es\ne\texttt{E} 时,每个操作的整数参数均经过加密。读入的每个参数 x 需要与上一次查询答案的低 3131 位按位异或。第一次查询之前,上一次查询答案为 00。两个查询之间的加入操作不会改变该值。

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;

当 s=Es=\texttt{E} 时,直接使用读入的参数。

输出格式

每遇到一次 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

数据范围

解密后的所有向量坐标满足 ∣x∣,∣y∣≤108|x|,|y|\le10^8。原赛数据分档如下,其中 TT 为查询当时已加入的向量数。

测试点 NN ss 其他约定
1–3 1≤N≤10001\le N\le1000 A 无
4 1≤N≤4×1051\le N\le4\times10^5 B 加入向量的横坐标单调不下降,且每次查询均满足 l=1,r=Tl=1,r=T
5–6 C 加入向量的横坐标单调不下降
7 D 每次查询均满足 l=1,r=Tl=1,r=T
8–9 E 无
10 F