P2574 The Art of XOR

AKN thought the first problem was too easy and refused to write it, so he started a new game. In the game, he found a pattern in the damage calculation, as follows: 1. There is a damage string, which is a string of length $n$ consisting only of the characters ``0`` and ``1``. The first character is considered the first position, i.e., indices start from $1$. 2. Given a range $[l,~r]$, the damage is the number of characters ``1`` within that range of the damage string. 3. The damage string can be modified by toggling all characters in $[l,~r]$: change every ``0`` to ``1`` and every ``1`` to ``0``. AKN wants to know the damage at certain times. Please help him compute it.

The first line contains two integers separated by a space, representing the length $n$ of the damage string and the number of operations $m$. The second line is a string $S$ of length $n$, representing the damage string. From the $3$-rd to the $(m + 2)$-nd line, each line contains three integers $op, l, r$, representing the type and interval of the $i$-th operation. The rules are: - If $op = 0$, toggle the characters in the interval $[l,~r]$ of the damage string: change ``0`` to ``1`` and ``1`` to ``0``. - If $op = 1$, query how many characters ``1`` are in the interval $[l,~r]$ of the damage string.

For each query, output a single line with one integer, representing the number of ``1`` in the interval.

Explanation for Sample Input/Output 1: The original damage string is ``1011101001``. For the first operation, toggle the characters in $[2,~4]$, and the damage string becomes ``1100101001``. For the second operation, query the number of ``1`` in $[1,~5]$, which is $3$. For the third operation, toggle the characters in $[3,~7]$, and the damage string becomes ``1111010001``. For the fourth operation, query the number of ``1`` in $[1,~10]$, which is $6$. For the fifth operation, toggle the characters in $[1,~4]$, and the damage string becomes ``0000010001``. For the sixth operation, query the number of ``1`` in $[2,~6]$, which is $1$. Constraints: - For $10\%$ of the testdata, it is guaranteed that $n, m \leq 10$. - For an additional $30\%$ of the testdata, it is guaranteed that $n, m \leq 2 \times 10^3$. - For $100\%$ of the testdata, it is guaranteed that $2 \leq n, m \leq 2 \times 10^5$, $0 \leq op \leq 1$, $1 \leq l \leq r \leq n$, and $S$ contains only the characters ``0`` and ``1``. Translated by ChatGPT 5