P5523 [yLOI2019] Pearls

> Do not sigh too much for farewells; at least the meeting was real. > Swaying between blooming and withering, time has never stopped. > Snow drifting at the edge of the world, never forgetting mountains and butterflies. > I heard someone let down the dark night, yet insisted on lighting the moon for the human world. > > — Yin Lin, “Pearls”.

Fusu gives you a small box for holding pearls. This box can add pearls without limit at both the left and right ends. Pearls in the box will line up into a sequence. Each time you add a pearl on the left end, it is inserted to the leftmost of the sequence; adding on the right end inserts it to the rightmost. Initially, the box is empty. Each pearl is either black or white. For convenience, we treat white as $0$ and black as $1$. In the mermaid world, combining color $A$ with color $B$ is defined as $A\operatorname{nand}B$, read as “$A$ NAND $B$”. Define $A \operatorname{nand} B = \operatorname{not} (A \operatorname{and}B)$, where $\operatorname{and}$ is the binary AND operation and $\operatorname{not}$ is the binary NOT operation. Define the combined value from position $x$ to position $y$ as: Starting from $x$ towards $y$, combine the first color with the second color, then combine the result with the third color, then combine that result with the fourth color, and so on, until combining with the color at position $y$. In particular, when $x = y$, the combined value is just that color. Formally, let $C_{x, y}$ be the combined value of sequence $A$ from $x$ to $y$. Then $$C_{x, y} = \begin{cases} C_{x, y - 1} \operatorname{nand} A_y & x < y \\ C_{x, y + 1} \operatorname{nand} A_y & x > y \\ A_x &x = y \end{cases}$$ For example, given the sequence $1, 1, 0, 0$, the combined value from $2$ to $4$ is $$(1 \operatorname{nand} 0) \operatorname{nand} 0 = 1 \operatorname{nand} 0 = 1$$ The combined value from $3$ to $1$ is $$(0 \operatorname{nand} 1) \operatorname{nand} 1 = 1 \operatorname{nand} 1 = 0$$ The combined value from $2$ to $2$ is $$1$$ Fusu will add some pearls to both ends of the box, or give a position $p$ and ask you for the combined value from the $1$st position (counting left to right) to the $p$-th position (counting left to right), or from the $1$st position (counting right to left) to the $p$-th position (counting right to left).

Each input file contains exactly one set of testdata. The first line contains an integer $n$, which is the number of operations performed by Fusu. Since reading each operation normally would require too much input, we use the following generator to generate each operation. ```cpp #include namespace Maker { typedef unsigned int uit; bool __sp; uit __x, __y, __z; int __type, __k, __m; template inline void qr(T &x) { char ch = getchar(), lst = ' '; while ((ch > '9') || (ch < '0')) lst = ch, ch = getchar(); while ((ch >= '0') && (ch 6; return __x; } inline uit Rand() { return __Next_Integer(); } template inline void Get_Nextline(Tx &x, Ty &y, Tz &z) { if (__m) { --__m; x = 0; y = 0; z = 0; qr(x); qr(y); qr(z); if (x == 0) { ++__k; } } else { x = Rand() & 1; y = Rand() & 1; if (__k == 0) { x = 0; } if (x == 0) { ++__k; if (__sp) { z = __type; } else { z = Rand() & 1; } } else { int dk = __k >> 1; if (dk == 0) { z = 1; } else { z = Rand() % dk + dk; } } } } } ``` For C/C++ users, we provide the generator code above (C users must submit in C++). Please copy it directly into your code. For non-C/C++ users, please implement the corresponding generator in your own language according to the code above. The following content is only for C++ users. Users of other languages should adapt it according to their language syntax. After reading $n$, you should call the `Begin` function in the `Maker` namespace, with parameter $n$. In other words, your code needs a statement like `Maker::Begin(n)`. After calling `Maker::Begin`, the generator starts working. There are $n$ operations. For each operation, call `Maker::Get_Nextline`, passing in three **integer** variables (say $x, y, z$). After each call, the values of $x, y, z$ will be modified and used as the parameters of the operation. The meanings are as follows: > Each operation has three integers as parameters, denoted $x, y, z$ in order. > > - If $x = 0$, this is an insertion operation. > - If $x = 1$, this is a query. > - If $y = 0$, the insertion is performed from the left side, or the query positions are counted from left to right. > - If $y = 1$, the insertion is performed from the right side, or the query positions are counted from right to left. > - If $x = 0$, then $z$ is an integer equal to $0$ or $1$, representing the color of the inserted pearl: $0$ means white and $1$ means black. > - If $x = 1$, then $z$ represents querying the combined value from the $1$st to the $z$-th position. The direction of combination and the direction of counting positions are determined by $y$. For C/C++ users, we provide a template program ([template program link](https://www.luogu.org/paste/lk7wn4a1)). In this program, the input and generator initialization are already done, and it can automatically obtain $x, y, z$. You only need to perform one operation each time as required by the statement and finally output the answer. You may choose whether to use this template; your final score is **unrelated** to your code content. **Special reminder: it is not recommended to use functions like `fread` to read a large amount of input and then parse $n$. If you insist on doing so, please rewrite the input-reading part in `Maker::Begin()`.** **Starting from the second line of the input, all data will be automatically read by the generator (including the second line), and you do not need to read it manually.** The second line of the input contains four integers $a, b, c, m$, where $a, b, c$ are parameters of the generator, and $m$ is the number of operations that need to be additionally read. To, in some sense, avoid “messy” solutions caused by fully random operations, we will first additionally read $m$ given operations, and then generate random ones. In the next $m$ lines, each line contains three integers $x,~y,~z$, representing one operation. Please note that these $m$ operations will be **automatically read** by the generator.

To avoid overly large output, output one line with four integers separated by spaces, representing among all queries: - How many queries have result $1$. - How many queries have an odd operation index and result $0$. - How many queries have an even operation index and result $1$. - How many queries have an operation index that is a multiple of $1024$ and result $0$. Define the operation index of the $i$-th operation as $i$. **Note that an insertion also counts as an operation.**

#### Explanation of Sample Input/Output 1 For the first operation, $x = 0, y = 1, z = 0$. Insert a $0$ at the right end, so the pearl sequence in the box is $\{0\}$. For the second operation, $x = 1, y = 0, z = 1$. Query the combined value from the first element to the first element counting from left to right. The answer is $0$. For the third operation, $x = 0, y = 1, z = 1$. Insert a $1$ at the right end, so the sequence becomes $\{0,~1\}$. For the fourth operation, $x = 1, y = 0, z = 1$. Query the combined value from the first element to the first element counting from left to right. The answer is $0$. For the fifth operation, $x = 0, y = 0, z = 0$. Insert a $0$ at the left end, so the sequence becomes $\{0,~0,~1\}$. For the sixth operation, $x = 0, y = 1, z = 1$. Insert a $1$ at the right end, so the sequence becomes $\{0,~0,~1,~1\}$. No query result satisfies any of the cases mentioned in the “Output Format”, so the output is `0 0 0 0`. --- #### Constraints and Conventions **This problem uses bundled subtasks, with a total of $7$ subtasks.** - Subtask 1 (5 points): $n = m = 0$. - Subtask 2 (15 points): $n = 1001$. - Subtask 3 (15 points): $n = 10^5 + 2$. - Subtask 4 (10 points): $n = 10^7 + 3$. For all operations with $x = 0$, it is guaranteed that $z = 1$. - Subtask 5 (10 points): $n = 10^7 + 4$. For all operations with $x = 0$, it is guaranteed that $z = 0$. - Subtask 6 (15 points): $n = 10^7 + 5$, $m = 0$. - Subtask 7 (30 points): $n = 10^7 + 6$. For all test cases, it is guaranteed that $0 \leq n \leq 10^7 + 6$, $0 \leq m \leq \min(n, 10^6)$, $x, y \in \{0, 1\}$, and for all operations with $x = 0$, it is guaranteed that $z \in \{0, 1\}$. Let $k$ be the number of pearls in the box at any query time; then for operations with $x = 1$, it is guaranteed that $1 \leq z \leq k$. There will be no query operation when the box is empty. --- #### Notes and Additional Information - Please pay attention to the impact of constant factors on program efficiency. - The last digit of $n$ can help you quickly determine which subtask the test case belongs to. - Since NAND and NOT are involved, NAND may not satisfy some common bitwise operation laws. Please be especially careful. - `std` uses C++, and the time limit is guaranteed to be at least $1.5$ times the runtime of `std`, **but it is not guaranteed that other languages can pass this problem**. - For C++ users, if you copy the generator above directly, it is guaranteed that the total runtime of the generator does not exceed 300 ms. Translated by ChatGPT 5