P3797 Youmu Chops the Wooden Rod

 Youmu is a half-human, half-phantom living in Hakugyokurou, and she has the ability to wield sword techniques.

One day, Youmu was practicing swordsmanship. There was an extremely long wooden rod on the ground, and Youmu cut it into $n$ equal segments. Now this rod can be regarded as composed of three kinds of small segments: the middle $n - 2$ segments are stumps cut on both sides, denoted by `X`; the leftmost segment and the rightmost segment each have a rounded end, denoted by `(` and `)` respectively. After eating her fill and feeling bored, Yuyuko decided to play a prank on Youmu. She brought many small wooden segments of these three types to replace part of the $n$ segments Youmu had cut, and then asked Youmu some questions. These operations are described as follows: - `1 x C` Replace the $x$-th small segment with type $C$, where $C$ is one of `X`, `(`, `)`. - `2 l r` Query how many complete rods are in the interval $[l, r]$ (inclusive). A complete rod must have `(` on the left end and `)` on the right end, and between them there may be zero or more `X` only. Although Youmu can count the answers to these questions, Yuyuko thinks she answers too slowly. Can you teach Youmu a faster method?

The first line contains two integers $n, m$, representing that there are $n$ segments and $m$ operations. The initial shape of the rod is `(XXXX...XXXX)`. Then follow $m$ lines, each describing one operation in one of the following forms, separated by spaces: - Type 1: `1 x C` — an integer $x$ and a character $C$. - Type 2: `2 l r` — two integers $l, r$. The meanings are as described above.

For each type 2 operation, output one line with one integer, representing the answer to that query.

For 30% of the testdata, $2 \leq n, m \leq 1 \times 10^3$. For 100% of the testdata, $2 \leq n, m \leq 2 \times 10^5$. by-orangebird. Translated by ChatGPT 5