UOJ Logo Universal Online Judge

UOJ

#90. 【集训队互测2015】Sone2

附件下载 统计

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)=maxs[1:k]=t[1:k]k

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

Jie 又定义了一个关于 a 串和 b 串的函数 F(a,b)F(a,b) 的值是一个二元组 (x,y),其中 x 为:

x=maxi=1|a|f(a[i:|a|],b)

y 表示满足 f(a[i:|a|],b)=xi 的个数。

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

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

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

输入格式

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

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

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

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

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

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

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

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

  1. x=1 则后面有两个整数 y,z,表示把 a 串中的第 y 位改成 z1yn1zΣ
  2. x=2 则后面有两个整数 y,z,表示询问的子串在 a 串中的区间 [y,z]1yzn
  3. x=3 则后面有两个整数 y,z,表示询问的两个后缀的第一个字符在 b 串中的位置。1y,zm
  4. x=4 则后面有四个整数 l1,r1,l2,r2,表示询问的两个子串在 b 串中的区间 [l1,r1][l2,r2]1l1r1m1l2r2m

输出格式

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 Σ 备注
1,2=1000100=1000100000
3,4=100000100=100000无操作二
5,6=10000030=100000
7,8=100000100000=100000只有操作三
9,10只有操作四
11,125b 串的生成方式是:人工确定每种字符出现的比例,
然后均匀随机选取一个满足这一比例的字符串作为 b
13,14
15,16
17,18100000
19,20

时间限制:2s

空间限制:256MB

来源

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

下载

样例数据下载