P4509 [CTSC2015] Onion

Xiao Cong and Xiao Xu are good friends. Since Xiao Cong pulled 1 UR and 2 SR in an 11-roll, Xiao Xu felt that Xiao Cong is very lucky, so he gave him a problem to test his luck. Xiao Xu first drew $N$ points on the plane, denoted as $P_1, P_2, ..., P_N$. He connected these $N$ points in order, that is, he connected $(P_1, P_2), (P_2, P_3), ..., (P_{N-1}, P_N)$ to obtain $N-1$ line segments. Then, each time Xiao Xu drew a line on the plane and asked how many segments this line intersects. In particular, intersection at a segment endpoint counts as intersecting, and if the line completely covers a segment, it also counts as intersecting. Such a question is obviously easy for Xiao Cong; he can give the correct answer by intuition alone thanks to his luck. To further test Xiao Cong’s luck, Xiao Xu increased the difficulty: in addition to each query, he would occasionally insert a new point $P$ between $P_i$ and $P_{i+1}$, then relabel all points in order; that is, the indices of points after $P_i$ increase by one, and point $P$ becomes the new point $P_{i+1}$. In particular, point $P$ can also be inserted before the first point or after the last point. Xiao Cong is still able to answer easily, so Xiao Xu raised the difficulty again: After each insertion or query, Xiao Xu recorded all the resulting segments and regarded them as a historical version. Historical version $T$ denotes the state after the $T$-th operation. The insertion operation was changed to: based on a certain historical version $T$, insert a point $P$ to obtain a new historical version. The query was changed to: for a historical version $T$, given a line, ask how many segments this line will intersect. Although Xiao Cong has great luck, he is helpless in the face of such a problem. He turns to you, a participant of CTSC, to help him solve it.

The first line contains three integers $N, M, C$, denoting the initial number of points, the total number of operations, and whether the data are encrypted. If $C=1$, it means the data are encrypted. In each query operation, $X_0, Y_0, X, Y$ and in each insertion operation, $X, Y$ are encrypted; you need to XOR them with last_ans to obtain the correct data, where last_ans is the answer to the previous query. Initially, last_ans $= 0$. The next $N$ lines each contain two integers; on the $i$-th line, the two integers denote the coordinates of $P_i$. The next $M$ lines describe Xiao Xu’s $M$ operations. The result after the $i$-th operation (1-indexed) is historical version $i$. For each operation, there is first a letter indicating the operation type. - If the letter is 'H', this is a query operation. Then five integers $T, X_0, Y_0, X, Y$ follow, meaning that under historical version $T$, Xiao Xu gives a line passing through $(X_0, Y_0)$ with direction $(X, Y)$, and Xiao Cong must answer how many segments it intersects. - If the letter is 'Z', this is an insertion operation. Then four numbers $T, i, X, Y$ follow, meaning that based on historical version $T$, Xiao Xu inserts a point with coordinates $(X, Y)$ after $P_i$. In particular, if $i=0$, it means the point is inserted before $P_1$.

For each query operation, output one line with one integer representing the correct answer Xiao Cong should give.

Sample explanation 1: For the third query, the line completely covers a segment, and Xiao Xu considers this as intersecting as well. Constraints and notes: All operations satisfy that in each query operation, $T$ is less than or equal to the current number of operations, and all input numbers are integers. There are the following 4 special testdata groups, which are pairwise disjoint: 1. For 10% of the testdata, $1 \le N, M \le 1000$. 2. For 15% of the testdata, for the $i$-th operation, $T = i - 1$. 3. For 15% of the testdata, $C=0$ and there are no modification operations. 4. For 15% of the testdata, for query operations, $Y=0$ (this refers to the decrypted data), i.e., the given line is parallel to the $x$-axis. The above testdata also guarantee $1 \le N, M \le 5 \times 10^4$. For 100% of the testdata, $1 \le N, M \le 10^5$, all coordinates are within $[-10^8, 10^8]$, and within each dataset the sum of answers over all queries does not exceed $10^6$. The number of insertion operations does not exceed $5 \times 10^4$. Note that these segments may intersect each other. Translated by ChatGPT 5