Sone 有一只调皮的宠物 Jie。
某天,Sone 在研究串匹配问题。
在他出门的时候在桌子上放了两个字符串:一个长度为
在走之前,Sone 严肃地警告 Jie:你不准动
于是,Jie 就只能调戏
设
Jie 定义了一个关于
即
Jie 又定义了一个关于
而
本来问题很简单的,但由于 Jie 太调皮了,一共有
- 他会修改
串的某一位,然后询问 。(操作后 不会还原) - 他会选择
串中的一个子串 ,询问 。 - 他会选择
串的两个后缀,并询问这两个后缀的最长公共前缀的长度。 - 他会选择
串的两个子串 ,并询问把 和 串联起来得到的字符串是否是 串的子串,是的话输出 “yes”,否则输出 “no”(不含引号)。
于是,Jie 困扰了,希望聪明的你能解决这个问题。
输入格式
设
第一行一个整数表示测试点编号。(样例和 Extra Test 中测试点编号为
第二行一个正整数表示
第三行
第四行一个正整数表示
第五行
第六行一个正整数表示询问个数
接下来
- 若
则后面有两个整数 ,表示把 串中的第 位改成 。 , 。 - 若
则后面有两个整数 ,表示询问的子串在 串中的区间 。 。 - 若
则后面有两个整数 ,表示询问的两个后缀的第一个字符在 串中的位置。 。 - 若
则后面有四个整数 ,表示询问的两个子串在 串中的区间 和 。 , 。
输出格式
有
样例一
input
0 10 1 2 3 3 3 1 2 3 2 1 3 1 3 1 10 3 1 3 4 3 3 2 2 2 2 10 1 3 2 2 7 9 2 7 10 2 3 9 2 2 8 1 7 1 1 4 2
output
1 yes 1 2 1 3 0 3 1 1 1 1 1 1 2 1 2 1
限制与约定
测试点编号 | 备注 | ||||
---|---|---|---|---|---|
1,2 | 无 | ||||
3,4 | 无操作二 | ||||
5,6 | 无 | ||||
7,8 | 只有操作三 | ||||
9,10 | 只有操作四 | ||||
11,12 | 然后均匀随机选取一个满足这一比例的字符串作为 | ||||
13,14 | |||||
15,16 | |||||
17,18 | 无 | ||||
19,20 |
时间限制:
空间限制:
来源
中国国家集训队互测2015 - By 王鉴浩