P6373 "StOI-1" IOI Counting

The weak (ruo, 蒻) `L_C_A` wants to learn about `IOI`, but he is too inexperienced to understand the problems, and can only count.

Given a string $S$ of length $n$, perform $m$ operations: Operation 1: $1$ $x$ $c$ means changing the $x$-th character to $c$ (where $c$ is only `I` or `O`). Operation 2: $2$ $l$ $r$ asks how many triples $(i,j,k)$ in the string $S$ satisfy: $S_{i}=$ `I`, $S_{j}=$ `O`, $S_{k}=$ `I`, and $l \le i < j < k \le r$.

The first line contains two positive integers $n$ and $m$. The next line contains a string $s$ of length $n$, and the next $m$ lines contain the operations. Their meanings are the same as described above.

Output multiple lines: for every operation 2, output the answer to the query, with each answer on its own line.

Constraints: For $20$% of the testdata: $1 \le n,m \le 100$, $1 \le l \le r \le n$. For another $20$% of the testdata: $1 \le n \le 10^{5}$, $m = 1$, $1 \le l \le r \le n$. For another $20$% of the testdata: $1 \le n,m \le 10^{5}$, $l = 1, r = n$. For $100$% of the testdata: $1 \le n,m \le 5 \times 10^{5}$, $1 \le l \le r \le n$. All input is guaranteed to be valid. Translated by ChatGPT 5