P6639 "JYLOI Round 1" Yield

Alice and Bob are playing a game. There are multiple piles of stones. The $k$-th pile has $p_k$ stones. The two players take turns making moves. On each move, you may choose any pile to operate on. Let $i$ be the number of stones in the chosen pile before this move, let $j$ be the number of stones to take in this move, and let $R$ be a given constant. The following conditions must be satisfied: $$1 \leq i + j \leq R,i \geq j \geq 1$$ The player who makes the opponent unable to move wins. During the game, both players use optimal strategies. There are multiple games. Specifically, there are $T$ operations in total, divided into two types: 1. "`change x`" means changing $R$ to $x$. 2. "`query n`" means starting one game. Then there are $n$ lines. The $i$-th line contains two positive integers $l_i$ and $r_i$, meaning that the number of piles and their sizes in this game can be described by these $n$ intervals. The $i$-th interval adds $(r_i - l_i + 1)$ new piles to this game, and for the $j$-th pile in this interval $(1 \leq j \leq r_i - l_i + 1)$, the number of stones is $(l_i + j - 1)$. For example, when $n = 2$ and the two intervals are $[1, 7]$ and $[2, 3]$, then this game has $[(7 - 1 + 1) + (3 - 2 + 1)] = 9$ piles, and the pile sizes are $1, 2, 3, 4, 5, 6, 7, 2, 3$. Since both Bob and Alice are very smart, and Bob does not want to win too many times, he wants to "yield" to Alice at appropriate moments. Therefore, he wants you to write a program. For each game, output "`1`" if the first player has a winning strategy, otherwise output "`0`". Can you do it?

The first line contains a positive integer $T$, meaning the number of operations. Then there are $T$ operations, in the format described above.

Output a single line: a string consisting of characters 0 and 1, with length less than $T$, whose meaning is as described above.

### Sample 1 Explanation There are $T=5$ operations in total. The 1st operation changes $R$ to 3. The 2nd operation starts a game. In this game, $n=1$ and the interval is $[2, 2]$, which means this game has $(2 - 2 + 1) = 1$ pile, and this pile has $(2 + 1 - 1) = 2$ stones. Since $R=3$, the first player can take at most 1 stone. If they take 2 stones, it does not satisfy the condition $1 \leq i + j \leq R$ in the **Description**. If they take 3 stones or more, it does not satisfy the condition $1 \leq i + j \leq R,i \geq j \geq 1$ in the **Description**. The meanings of $i$, $j$, and $R$ are as described above. After the first player takes stones, the only pile has 1 stone left. Then the second player takes 1 stone and makes the first player unable to move, so the first player loses. Since this is the only possible move, the first player is guaranteed to lose, so the first player has no winning strategy, and the output is "`0`". The 3rd operation changes $R$ to 4. The 4th operation starts a game. In this game, $n=1$ and the interval is $[2, 2]$, which means this game has $(2 - 2 + 1) = 1$ pile, and this pile has $(2 + 1 - 1) = 2$ stones. The first player can take at most 2 stones, because if the first player takes 3 stones or more, it does not satisfy the condition $1 \leq i + j \leq R,i \geq j \geq 1$ in the **Description**. The meanings of $i$, $j$, and $R$ are as described above. Since when the first player chooses to take 2 stones, they take all stones and make the second player unable to move, the first player must win, and the output is "`1`". The 5th operation changes $R$ to 2. ____________ ### Constraints For $100\%$ of the data, it holds that $1 \leq T \leq 10^5, 2 \leq R \leq 10^{15}, 0 \leq l_i \leq r_i < R, 1 \leq \sum{n} \leq 5 \times 10^5$, and the first operation is guaranteed to be a type 1 operation. For testdata 1~2, it holds that $T \leq 10, l_i \leq r_i \leq 3$, and in a single game the number of piles will not exceed 4. For testdata 3~6, it holds that $T \leq 100, R \leq 100, \sum{n} \leq 100$. For testdata 7~10, it holds that $T \leq 10, R \leq 10^5, \sum{n} \leq 50$. For testdata 11~12, it holds that $R \leq 5 \times 10^3, \sum{n} \leq 5 \times 10^5$, and there is only one modification operation. For testdata 13~16, it holds that $T \leq 10^5,R \leq 10^5,\sum{n} \leq 5 \times 10^5$. There are 20 testdata points in total, 5 points each. ### Source "JYLOI Round 1" E Idea / Solution / Data: abcdeffa Translated by ChatGPT 5