P6373 「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

输入格式

无

输出格式

无

说明/提示

对于 $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$。所有数据保证合法。