#P17998. String Workshop
String Workshop
String Workshop
题目描述
Cleopatra 会将一个字符串按字母升序排序。她只能交换相邻字符:交换当前字符串的第 个和第 个字符,需要支付 枚金币。相同位置若交换多次,每次都要付费。她会选择总费用最小的交换方案。
Catherine 有一个长度为 、仅包含大写英文字母的字符串 。请按顺序处理以下操作:
1 i c:将 替换为字符 。2 l r:复制子串 ,求 Cleopatra 将这个副本排序所需的最少金币数;原字符串不变。3 l r:求将子串 排序所需的最少金币数,并将该子串替换为其排序结果。
对子串计费时,从子串开头重新编号为 ,不使用原字符串中的位置。
输入格式
第一行一个整数 ,表示测试用例数,。
每个测试用例的第一行包含 ,分别表示字符串长度和操作数;。
第二行是长度为 的大写英文字母字符串。随后 行描述操作,格式如上。更新位置满足 ,字符为 A 至 Z;区间满足 。
每个测试用例至少有一次第 2 或第 3 类操作。所有测试用例的 之和、 之和分别不超过 。
输出格式
按操作顺序输出每次第 2、3 类操作的最小费用,每个答案单独一行。
样例 1
输入
1
5 20
DBCAA
2 1 5
2 2 4
1 3 Z
2 1 3
3 1 5
2 1 5
1 5 A
3 2 4
2 1 5
1 1 C
2 1 2
3 4 5
2 3 5
1 2 B
2 1 5
3 1 1
2 1 1
1 4 D
2 1 5
3 1 5
输出
18
3
1
16
0
0
7
1
1
1
9
0
0
3
3
样例 2
输入
3
3 5
CBA
2 1 3
3 1 3
2 1 3
1 2 C
2 1 2
5 5
ABCDE
2 2 5
1 5 A
2 1 5
3 1 5
2 1 5
6 5
YYYYYY
2 1 6
1 3 A
2 1 6
3 2 5
2 1 6
输出
4
4
0
0
0
9
9
0
0
3
1
1