P8263 [Ynoi Easy Round 2020] TEST_8

Given a $01$ string $S$ of length $n$ (a sequence consisting of $0$ and $1$, indexed by integers from $1$ to $n$). The following operations are supported: Operation 1: given $l, r, k$, repeat the substring of the $01$ string from index $l$ to $r$ for $k$ times and put it back in place. Operation 2: given $l, r, k$, repeat the substring of the $01$ string from index $l$ to $r$ for $k$ times with reversal (specifically, for the $i$-th repetition ($1 \leq i \leq k$), if the binary representation of $i - 1$ contains an odd number of $1$, then this repetition should be reversed left to right; otherwise it remains unchanged), and finally put it back in place. Operation 3: given $l, r$, delete the substring of the $01$ string from index $l$ to $r$. Operation 4: given $k$, find the position of the $k$-th $1$ in the $01$ string from left to right. If $k$ exceeds the number of $1$ in the $01$ string, output $-1$.

The first line contains an integer $n$. The next line contains a $01$ string of length $n$. The next line contains an integer $m$. The next $m$ lines each start with an integer $op$ indicating the operation type. If $op = 1$ or $op = 2$, the line then contains three integers $l, r, k$. If $op = 3$, the line then contains two integers $l, r$. If $op = 4$, the line then contains one integer $k$.

For each operation 4, output one line representing the answer.

Idea: ccz181078, Solution: ccz181078, Code: ccz181078, Data: ccz181078. It is guaranteed that $1 \leq l \leq r \leq$ the length of the $01$ string before the operation. In operations $1, 2, 4$, $1 \leq k \leq 10^8$. For $20\%$ of the testdata, $n, m$, and the length of the $01$ string never exceed $20$. For $40\%$ of the testdata, there is only one operation 4, and there is no operation 2. For $100\%$ of the testdata, $1 \leq n, m \leq 10^5$, and the length of the $01$ string never exceeds $10^8$. Sample explanation: The 1st operation: 1[10]11100010->111100010, deleted 10. The 2nd operation: 11110[001]0->11110[001,100,100,001,100]0->111100011001000011000, repeated 001 for 5 times, where the 2nd, 3rd, and 5th times are reversed. The 3rd operation: 1[1110]0011001000011000->1[1110,1110,1110]0011001000011000->11110111011100011001000011000, repeated 1110 for 3 times. The 4th operation: 111101110[1]1100011001000011000, the 8th $1$ is at the 10th position in the $01$ string. The 5th operation: there is no 100th $1$, output -1. Translated by ChatGPT 5