P3309 [SDOI2014] Vector Set

Maintain a set of vectors and support the following operations online: - `A x y` ($|x|, |y| \le 10^8$): insert the vector $(x, y)$. - `Q x y l r` ($|x|, |y| \le 10^8$, $1 \le l \le r \le t$, where $t$ is the number of vectors already inserted): query the maximum dot product between the vector $(x, y)$ and each of the vectors from the $l$-th to the $r$-th inserted. Initially, the set is empty.

The first line contains an integer $N (1 \le N \le 4 \times 10^5)$ and a character $s$, representing the number of operations and the data category, respectively. Then follow $N$ lines, each containing one operation in the format described above. Note that when $s$ is not `E`, all integers in the input are encrypted. You can use the following program to obtain the original input: ``` inline int decode(int x, long long lastans) { return x ^ (lastans & 0x7fffffff); } ``` Here, $x$ is the number read by your program, and `lastans` is the answer to the most recent previous query. Before the first query, `lastans` is $0$. Note: the dot product of vectors $(x, y)$ and $(z, w)$ is defined as $xz + yw$.

For each `Q` operation, output an integer representing the answer.

Sample explanation: after decryption, the input is ``` 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 ``` Translated by ChatGPT 5