#1048. 您太强了

内存限制:512 MiB 时间限制:1500 ms 输入文件:orz.in 输出文件:orz.out
题目类型:传统 评测方式:文本比较
上传者: H6_6Q

题目描述

给定一个长度为 n 且只由 \mathtt{o} , \mathtt{r} , \mathtt{z} 三个英文字母组成的字符串 s ,现在有 q 次操作。

每次操作都有两种可能:

  1. 给定一个整数 x ,表示在 s_x 后插入一个 \mathtt{o} 字符。

  2. 给定两个整数 l,r ,查询 s_l,s_{l+1}\ ...\ s_{r-1},s_r 这个字符串区间中为 \mathtt{orz} 的子序列的数量。

对于一个字符串 t ,其子序列的定义为:选出若干个下标 p_1,p_2\ ...\ p_k\ (p_1 < p_2 <...<p_k\ ,\ k \le |t|) ,那么 t_{p_1},t_{p_2}\ ...\ t_{p_k} 就是 t 的一个子序列。

输入格式

第一行输入两个整数 n,q 表示字符串长度和询问次数。

第二行输入一个长度为 n 的字符串。

接下来 q 行,每行输入一个整数 op 表示操作编号。

  • 如果 op=1 ,那么接下来输入一个整数 x 表示在 s_x 后插入一个 \mathtt{o} 字符。

  • 如果 op=2 ,那么接下来输入两个整数 l,r 表示要查询的区间是 s_l,s_{l+1}\ ...\ s_{r-1},s_r

输出格式

对于每个询问输出一个整数表示该区间内为 \mathtt{orz} 的子序列的数量。

样例

输入样例 #1:

6 3
orzorz
2 4 6
2 1 3
2 1 6

输出样例 #1:

1
1
4

输入样例 #2:

5 3
orrzz
2 1 5
1 1
2 1 6

输出样例 #2:

4
8

数据范围与提示

【样例解释】

【数据范围与约定】

对于全部的数据,保证 1 \le n,q,x \le 3 \times 10^5 , s_i \in \left\{\text{o,r,z}\right\} , 1 \le l \le r \le n

特殊性质 \text{A} :没有 1 操作。

特殊性质 \text{B} :只有一次 2 操作。

测试点编号 分值 n,q= 特殊性质 \text{A} 特殊性质 \text{B}
1,2 10 100 \times \surd
3,4 500 \surd \times
5\sim7 15 3000
8\sim12 25 300000
13\sim14 10 \times \surd
15\sim20 30 \times

【提示】

请注意常数因子对程序速度的影响