字符串中的字母可以形象的看作小塔公司里的商家,有实力的商家能够不断的取代小的商家。
具体表现为:每过一个单位时间,当前商家会被替代为和其相邻位置的最大商家。商家的大小根据Ascii码顺序排序:a<b<...<z
为了提前制定防范措施,小塔需要知道字符串s变为只含单个商家的最少单位时间。但是这样似乎难不倒你,所以小塔会提出多个区间[l,r]的操作空间或询问,格式如下;
操作一:将字母串s的第i个商家替代为商家p;
操作二:询问当前字符串s的[l,r]这个区间变成单个商家需要的最少单位时间;每次操作二的询问均相互独立、互不影响;
小塔需要你帮助他完成这个任务
每个测试文件均包含多组测试数据。第一行输入一个整数T(1≤T≤100)代表数据组数,每组测试数据描述如下:
第一行输入两个整数n,q(1≤n,q≤2×105),字符串长度、操作次数。
第二行输入一个长度为n、且仅由小写字母构成的字符串s
此后q行,先输入一个整数op(1≤op≤2)表示操作类型,随后:
当op=1时,在同一行上输入一个整数i和一个字符p(1≤i≤n;a≤p≤z)表示把字符si修改为字符P
当op=2时,在同一行上输入两个整数l,r(1≤l≤r≤n)表示询问的字符串区间。
除此之外,保证所有的n,q之和均不超过2×105
对于每个操作二,在一行上输出一个整数,代表当前询问区间内变成单个字符需要的最少单位时间。
输入
2
7 5
adbfdca
2 5 7
1 4 d
2 1 7
2 1 4
2 4 7
5 3
aaaaa
2 1 4
1 2 f
2 1 4
输出
2
2
1
2
0
2
说明
对于第一组测试数据的第一次询问,区间为[5,7]:第一个单位时间,s=ddc、第二个单位时间,s=ddd。故最少单位时间为2。
扫码备注加群即可,期待您的到来~
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.