修复后 md: https://www.luogu.com.cn/paste/a79nzbf1

---

妖梦斩木棒

题目背景

妖梦是住在白玉楼的半人半灵，拥有使用剑术程度的能力。

题目描述

有一天，妖梦正在练习剑术。地面上摆放了一支非常长的木棒，妖梦把它们切成了等长的 $n$ 段。现在这个木棒可以看做由三种小段构成，中间的 $n-2$ 段都是左右都被切断的断头，我们记做 $\mathtt{X}$，最左边的一段和最右边的一段各有一个圆头，记做 $\mathtt{(}$ 和 $\mathtt{)}$。幽幽子吃饱后闲来无事，决定戏弄一下妖梦。她拿来了许多这样的三种小段木棒，来替换掉妖梦切下来的 $n$ 段中的一部分，然后问妖梦一些问题。这些操作可以这样描述:

1 x C：将第 $x$ 个小段的木棒替换成 $C$ 型，$C$ 只会是 $\mathtt{X},\mathtt{(},\mathtt{)}$ 中的一种。

2 l r：询问妖梦从第 $l$ 段到第 $r$ 段之间（含 $l,r$），有多少个完整的木棒。

完整的木棒左右两端必须分别为 $\mathtt{(}$ 和 $\mathtt{)}$，并且中间要么什么都没有，要么只能有 $\mathtt{X}$。

虽然妖梦能够数清楚这些问题，但幽幽子觉得她回答得太慢了，你能教给妖梦一个更快的办法吗？

输入格式

第一行两个整数 $n,m$，$n$ 表示共有 $n$ 段木棒，$m$ 表示有 $m$ 次操作。

木棒的初始形状为 $\mathtt{(XXXXXX......XXXXXX)}$。

接下来 $m$ 行，每行三个整数/字符，用空格隔开。第一个整数为 $1$ 或 $2$，表示操作的类型，若类型为 $1$，则接下来一个整数 $x$，一个字符 $C$。若类型为 $2$，接下来两个整数 $l,r$。含义见题目描述。

输出格式

对于每一个操作 $2$，输出一行一个整数，表示对应询问的答案。

样例 #1

样例输入 #1

4 4
2 1 4
2 2 4
1 2 (
2 2 4

样例输出 #1

1
0
1

提示

对于 $30\%$ 的数据，$1\leq n,m\leq 10^3$。

对于 $100\%$ 的数据，$1\leq n,m\leq 2\times 10^5$。

by-orangebird.