「StOI-1」IOI计数
题目背景
蒻`L_C_A`想了解一下`IOI`,可他太菜了,看不懂题目,只会数数。
题目描述
给定一个长度为 $n$ 字符串 $S$ ,同时进行 $m$ 次操作:
操作1:$1$ $x$ $c$ 表示将第 $x$ 个字符改为 $c$( $c$ 只会为 `I` 或 `O` )。
操作2:$2$ $l$ $r$ 询问字符串 $S$ 中有多少对三元组 $(i,j,k)$ 满足:
$S_{i}=$ `I` ,$S_{j}=$ `O` ,$S_{k}=$ `I` 并且 $l≤i<j<k≤r$ 。
输入输出格式
输入格式
输入第一行两个正整数 $n$ 和 $m$ 。
接下来一行是长度为 $n$ 的字符串 $s$ ,接下来 $m$ 行是操作。
含义均如题。
输出格式
输出若干行:对于所有操作2,输出查询的答案,要求每个答案之间换行。
输入输出样例
输入样例 #1
4 3
IOOI
2 1 4
1 1 O
2 1 2
输出样例 #1
2
0
输入样例 #2
10 10
IIOOIOIIIO
1 1 I
2 1 7
1 5 O
2 5 9
1 4 I
1 10 I
2 1 10
2 5 10
2 2 8
2 3 9
输出样例 #2
11
0
34
0
11
6
说明
对于 $20$% 的数据:$1 ≤ n,m ≤ 100$,$1 ≤ l ≤ r ≤ n$;
对于另 $20$% 的数据:$1 ≤ n ≤ $ $10^{5}$,$m = 1$,$ 1 ≤ l ≤ r ≤ n$;
对于另 $20$% 的数据:$1 ≤ n,m ≤ $ $10^{5}$,$l=1,r=n$;
对于 $100$% 的数据:$1 ≤ n,m ≤ $ $5$ $\times$ $10^{5}$,$1 ≤ l ≤ r ≤ n$。
所有数据保证合法。