#1975. Sone2

    ID: 1975 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest38来源:qoj.ac数据:公开样例字符串线段树分块后缀数组

Sone2

Sone2

题目描述

标题: Sone2 - Problem - QOJ.ac

#4255. Sone2

Statistics

The problem was used in the following contests:

Sone 有一只调皮的宠物 Jie。

某天,Sone 在研究串匹配问题。

在他出门的时候在桌子上放了两个字符串:一个长度为 的字符串 和一个长度为 的字符串 。设 为字符串的字符集大小,即字符串中每个字符都是 到 之间的整数。

在走之前,Sone 严肃地警告 Jie:你不准动 串,那个串很重要!

于是,Jie 就只能调戏 串。

设 表示 串第 个字符到第 个字符之间的子串。特别地,当 时, 表示空串。

Jie 定义了一个关于 串和 串的函数:

即 和 的最长公共前缀的长度。

Jie 又定义了一个关于 串和 串的函数 。 的值是一个二元组 ,其中 为:

而 表示满足 的 的个数。

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

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

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

输入格式

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

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

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

第三行 个 到 间的整数表示 串。

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

第五行 个 到 间的整数表示 串。

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

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

  1. 若 则后面有两个整数 ,表示把 串中的第 位改成 。,。
  2. 若 则后面有两个整数 ,表示询问的子串在 串中的区间 。。
  3. 若 则后面有两个整数 ,表示询问的两个后缀的第一个字符在 串中的位置。。
  4. 若 则后面有四个整数 ,表示询问的两个子串在 串中的区间 和 。,。

输出格式

有 行,每行对应每种操作的答案。

样例一

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,1415,1617,18无19,20

时间限制:

空间限制:

来源

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

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

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
1
yes
1 2
1 3
0 3
1 1
1 1
1 1
2 1
2 1