P11657 "FAOI-R5" datealive

 

Given a sequence $c_1,c_2,\cdots,c_n$ of length $n$, where $c_i\in\{0,1\}$. Each element corresponds to a parenthesis: if $c_i=0$, the parenthesis at this position is a left parenthesis; if $c_i=1$, it is a right parenthesis. Let $f(l,r)$ denote whether the parenthesis sequence in the interval $[l,r]$ is valid. If the sequence formed by $c_l,c_{l+1},\cdots,c_r$ is a valid parenthesis sequence, then $f(l,r)=1$; otherwise, $f(l,r)=0$. Definition of a valid parenthesis sequence: - The empty string is a valid parenthesis sequence. - If `A` is a valid parenthesis sequence, then `(A)` is a valid parenthesis sequence. - If `A` and `B` are valid parenthesis sequences, then `AB` is a valid parenthesis sequence. You need to perform $q$ operations **online**, of two types: - `1 l r`: Query $\max\limits_{[l',r']\in[l,r]}\{(r'-l'+1)\cdot f(l',r')\}$, i.e., query the length of the longest valid parenthesis substring within $[l,r]$. - `2 l r`: For all $i\in[l,r]$, modify $c_i$ to $(1-c_i)$, i.e., flip every parenthesis in $[l,r]$ one by one.

The first line contains two positive integers $n,q$, representing the sequence length and the number of operations. The next line contains $n$ non-negative integers $c_1,c_2\cdots,c_n$, representing the initial sequence. The next $q$ lines each contain three positive integers $op,l',r'$, representing the operation type and the encrypted $l,r$. To enforce online processing, the data is encrypted and must be decrypted as follows: let $p$ be the answer to the previous query operation, or $0$ if there is none. Compute $l=((l'+p)\bmod n)+1$ and $r=((r'+p)\bmod n)+1$. If $l>r$, swap $l,r$. Here, $op,l,r$ are the three parameters of the operation. If $op=1$, it means the `1 l r` operation described above; if $op=2$, it means the `2 l r` operation described above.

For each query, output one line with a non-negative integer representing the answer.

### Sample 1 Explanation The decrypted result is as follows: ``` 10 10 0 1 1 0 0 1 0 0 1 1 2 8 9 2 1 6 2 2 6 2 7 8 2 2 8 2 5 6 2 4 5 1 3 6 1 6 9 1 10 10 ``` After $7$ modifications, the parenthesis string becomes $)((())()()$. - For the first query, take the substring $[3,6]$ to get $(())$. The whole substring is a valid parenthesis sequence, so the answer is $6-3+1=4$. - For the second query, take the substring $[6,9]$ to get $)()($. The substring $[7,8]$ is the longest valid parenthesis substring within it, so the answer is $8-7+1=2$. - For the third query, take the substring $[10,10]$ to get $)$. The valid parenthesis substring within this substring is the empty string, so the answer is $0$. ### Constraints and Notes **This problem uses bundled testdata.** | Subtask ID | $n \le$ | $q \le$ | Score | Special Property | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $100$ | $100$ | $10$ | × | | $2$ | $2 \times 10^4$ | $2 \times 10^4$ | $10$ | × | | $3$ | $4 \times 10^6$ | $10^5$ | $20$ | $\checkmark$ | | $4$ | $10^5$ | $10^5$ | $30$ | × | | $5$ | $4 \times 10^6$ | $10^5$ | $30$ | × | Special property: it is guaranteed that there are no modification operations. For all testdata, $1 \le n\le 4 \times 10^6$, $1\le q \le 10^{5}$, $1 \le l',r' \le n$, $op\in\{1,2\}$, and $c_i\in\{0,1\}$. For this problem, except for Subtask #3, it is guaranteed that the operation type is generated randomly, i.e., each time a random number from $\{1,2\}$ is chosen (with probability $50\%$ for both $1$ and $2$) as $op$. A large sample is provided in the problem attachments. Translated by ChatGPT 5