QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 256 MB Total points: 100 Hackable ✓
[0]

# 4255. Sone2

Statistics

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

st 的最长公共前缀的长度。

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) = xi 的个数。

本来问题很简单的,但由于 Jie 太调皮了,一共有 q 个时刻,每个时刻他会有四种行为:

  1. 他会修改 a 串的某一位,然后询问 F(a,b)。(操作后 a 不会还原)
  2. 他会选择 a 串中的一个子串 c,询问 F(c,b)
  3. 他会选择 b 串的两个后缀,并询问这两个后缀的最长公共前缀的长度。
  4. 他会选择 b 串的两个子串 s_1,s_2,并询问把 s_1s_2 串联起来得到的字符串是否是 b 串的子串,是的话输出 “yes”,否则输出 “no”(不含引号)。

于是,Jie 困扰了,希望聪明的你能解决这个问题。

输入格式

\Sigma 为字符串的字符集大小,即字符串中每个字符都是 1\Sigma 之间的整数。

第一行一个整数表示测试点编号。(样例和 Extra Test 中测试点编号为 020 间的任意整数)

第二行一个正整数表示 a 串的长度 n

第三行 n1\Sigma 间的整数表示 a 串。

第四行一个正整数表示 b 串的长度 m

第五行 m1\Sigma 间的整数表示 b 串。

第六行一个正整数表示询问个数 q

接下来 q 行表示操作,每行包含若干个整数。第一个整数 x 表示操作类型:

  1. x=1 则后面有两个整数 y,z,表示把 a 串中的第 y 位改成 z1 \leq y \leq n1 \leq z \leq \Sigma
  2. x=2 则后面有两个整数 y,z,表示询问的子串在 a 串中的区间 [y, z]1 \leq y \leq z \leq n
  3. x=3 则后面有两个整数 y,z,表示询问的两个后缀的第一个字符在 b 串中的位置。1 \leq y, z \leq m
  4. 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 m1 \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 5b 串的生成方式是:人工确定每种字符出现的比例,
然后均匀随机选取一个满足这一比例的字符串作为 b
13,14
15,16
17,18\leq 100000
19,20

时间限制:2\texttt{s}

空间限制:256\texttt{MB}

来源

中国国家集训队互测2015 - By 王鉴浩