Sone 有一只调皮的宠物 Jie。
某天,Sone 在研究串匹配问题。
在他出门的时候在桌子上放了两个字符串:一个长度为 n 的字符串 a 和一个长度为 m 的字符串 b。设 Σ 为字符串的字符集大小,即字符串中每个字符都是 1 到 Σ 之间的整数。
在走之前,Sone 严肃地警告 Jie:你不准动 b串,那个串很重要!
于是,Jie 就只能调戏 a 串。
设 a[l:r] 表示 a 串第 l 个字符到第 r 个字符之间的子串。特别地,当 l>r 时,a[l:r] 表示空串。
Jie 定义了一个关于 s 串和 t 串的函数:
f(s,t)=max
即 s 和 t 的最长公共前缀的长度。
Jie 又定义了一个关于 a 串和 b 串的函数 F(a,b)。F(a,b) 的值是一个二元组 (x,y),其中 x 为:
x=\max_{i=1}^{\lvert a \rvert} f(a[i:\lvert a \rvert],b)
而 y 表示满足 f(a[i:\lvert a \rvert], b) = x 的 i 的个数。
本来问题很简单的,但由于 Jie 太调皮了,一共有 q 个时刻,每个时刻他会有四种行为:
- 他会修改 a 串的某一位,然后询问 F(a,b)。(操作后 a 不会还原)
- 他会选择 a 串中的一个子串 c,询问 F(c,b)。
- 他会选择 b 串的两个后缀,并询问这两个后缀的最长公共前缀的长度。
- 他会选择 b 串的两个子串 s_1,s_2,并询问把 s_1 和 s_2 串联起来得到的字符串是否是 b 串的子串,是的话输出 “yes”,否则输出 “no”(不含引号)。
于是,Jie 困扰了,希望聪明的你能解决这个问题。
输入格式
设 \Sigma 为字符串的字符集大小,即字符串中每个字符都是 1 到 \Sigma 之间的整数。
第一行一个整数表示测试点编号。(样例和 Extra Test 中测试点编号为 0 到 20 间的任意整数)
第二行一个正整数表示 a 串的长度 n。
第三行 n 个 1 到 \Sigma 间的整数表示 a 串。
第四行一个正整数表示 b 串的长度 m。
第五行 m 个 1 到 \Sigma 间的整数表示 b 串。
第六行一个正整数表示询问个数 q。
接下来 q 行表示操作,每行包含若干个整数。第一个整数 x 表示操作类型:
- 若 x=1 则后面有两个整数 y,z,表示把 a 串中的第 y 位改成 z。1 \leq y \leq n,1 \leq z \leq \Sigma。
- 若 x=2 则后面有两个整数 y,z,表示询问的子串在 a 串中的区间 [y, z]。1 \leq y \leq z \leq n。
- 若 x=3 则后面有两个整数 y,z,表示询问的两个后缀的第一个字符在 b 串中的位置。1 \leq y, z \leq m。
- 若 x=4 则后面有四个整数 l_1,r_1,l_2,r_2,表示询问的两个子串在 b 串中的区间 [l_1,r_1] 和 [l_2,r_2]。1 \leq l_1 \leq r_1 \leq m,1 \leq l_2 \leq r_2 \leq m。
输出格式
有 q 行,每行对应每种操作的答案。
样例一
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
限制与约定
测试点编号 | n | m | q | \Sigma | 备注 |
---|---|---|---|---|---|
1,2 | = 1000 | \leq 100 | = 1000 | \leq 100000 | 无 |
3,4 | = 100000 | \leq 100 | = 100000 | 无操作二 | |
5,6 | = 100000 | \leq 30 | = 100000 | 无 | |
7,8 | = 100000 | \leq 100000 | = 100000 | 只有操作三 | |
9,10 | 只有操作四 | ||||
11,12 | \leq 5 | b 串的生成方式是:人工确定每种字符出现的比例, 然后均匀随机选取一个满足这一比例的字符串作为 b | |||
13,14 | |||||
15,16 | |||||
17,18 | \leq 100000 | 无 | |||
19,20 |
时间限制:2\texttt{s}
空间限制:256\texttt{MB}
来源
中国国家集训队互测2015 - By 王鉴浩