P10012 [CTT Mutual Test 2023] Sunset Coral

You are given a bracket string of length $n$ consisting of square brackets and parentheses. A string $S$ is defined to be valid if and only if it satisfies one of the following: 1. $S$ is an empty string. 1. $S = [T]$ and $T$ is valid. 1. $S = (T)$ and $T$ is valid. 1. $S = TU$ and both $T$ and $U$ are valid. For example, ```()``` and ```[()]``` are valid bracket strings, but ```[()]())``` is not. Define an operation as follows: choose an interval $[l, r]$, and for every character in the interval, change square brackets to parentheses, and change parentheses to square brackets. Define the value $val(S)$ of a bracket string $S$ as: if this string can be turned into a valid string using operations, then $val(S)$ is the minimum number of operations needed; otherwise, it is $0$. You are given $q$ update/query operations of two types: 1. Update: given an interval $[l, r]$, change every character in the interval from square brackets to parentheses, and from parentheses to square brackets. 2. Query: given an interval $[l, r]$, compute $\sum_{[l', r'] \in [l, r]} val(s[l', r'])$.

The first line contains four integers $n, q, T, subtaskid$, representing the string length, the number of operations, the parameter for forcing online processing, and the subtask ID. The next line contains a string of length $n$. Then follow $q$ lines, each containing three numbers $opt, L, R$, representing one operation. Online is enforced. The actual $l = \min((L + T \cdot lastans) \bmod n + 1, (R + T \cdot lastans) \bmod n + 1)$ and $r = \max((L + T \cdot lastans) \bmod n + 1, (R + T \cdot lastans) \bmod n + 1)$, where $lastans$ is the answer to the previous query; if there was no previous query, then it is $0$. **Please note that even for offline subtasks, it is still possible that $L \neq l$ and $R \neq r$.**

Output several lines. For each query, output one answer.

For all testdata, $1 \le n, q \le 5\cdot 10^5$, $0 \le T \le 10^9$, $1 \le l, r \le n$, and $1 \le opt \le 2$. | Subtask ID | $n, q \le$ | Special Property | Score | | :--------: | :--------: | :--------------: | :---: | | 1 | $100$ | E | 5 | | 2 | $6000$ | E | 5 | | 3 | $10^5$ | AE | 5 | | 4 | $2\cdot 10^5$ | BE | 5 | | 5 | $2\cdot 10^5$ | CDE | 5 | | 6 | $2\cdot 10^5$ | CE | 10 | | 7 | $2\cdot 10^5$ | DE | 10 | | 8 | $2\cdot 10^5$ | E | 10 | | 9 | $2\cdot 10^5$ | None | 20 | | 10 | $5\cdot 10^5$ | None | 25 | Property A: At each position, each of the four bracket types has probability $\frac{1}{4}$. Property B: It is guaranteed that there are no updates. Property C: It is guaranteed that each update is a single-point update. Property D: It is guaranteed that for the query interval $[l, r]$, $S[l, r]$ can be turned into a valid string after some operations, and there does not exist another $k \in [l, r)$ such that $S[l, k]$ can be turned into a valid string after some operations. Property E: It is guaranteed that $T = 0$, i.e., the problem can be solved offline. # Input Format # Output Format # Hint Translated by ChatGPT 5