#P11740. [集训队互测 2015] ydc 的字符串
[集训队互测 2015] ydc 的字符串
题目描述
ydc 很喜欢字符串,他有特别的视角看待字符串。
字符串是由字符组成的。字符一共 种,分别编号为 。
对于整数 ,如果两个字符串 满足在 最前面加一个编号在区间 以内的字符后两串相等,那么就称 能通过 与 相等。
ydc 将给你 个字符串,编号为 ,并要求进行 次操作,每次操作形如以下四种之一:
- 操作 0:在第 个字符串后面加上一个字符 。保证 ,。
- 操作 1:询问当前第 个字符串中有多少个子串满足在第 个操作过后的第 个字符串能通过 与该子串相等。 是小于当前操作编号的非负整数, 表示在所有操作之前。保证 ,。
- 操作 2:将第 个字符串改成第 个字符串。保证 。
- 操作 3:给你一个字符串 ,对于这 个串中的每个串询问有多少个子串满足 能通过 与该子串相等,。
另外,输入文件可能被加密来强制你在线进行操作。
输入格式
第一行三个整数数,,分别表示字符串个数,字符集大小,以及是否数据是否被加密。如果数据被加密,则 的值为 ,否则为 。
如果数据被加密,令 为当前操作之前最后一个输出的数(如果此前没有输出则 )。那么当前操作中读入的所有数均被加密成了原数异或 。
字符串将按照如下格式给出:第一个数为一个正整数 表示字符串的长度,后面跟着 个整数,两两之间用空格隔开,表示每个位置上的字符编号。
接下来 行,第 行将给出第 个字符串。
再读入一个正整数 ,即操作数。
接着 行,每行为一个操作的信息。每行第一个数为操作的类型编号。
- 如果是操作 ,那么接着两个整数 。
- 如果是操作 ,那么接着五个整数 。
- 如果是操作 ,那么接着两个整数 。
- 如果是操作 ,那么接着两个整数 和一个字符串 。
输出格式
按照输入顺序回答询问。
对于每个操作 ,输出一行一个整数表示答案。
对于每个操作 ,输出一行 个整数分别表示每个字符串中满足条件的子串个数。
3 3 0
5 0 1 1 1 2
1 1
2 1 1
4
0 1 1
3 0 1 1 1
2 2 1
1 1 2 0 0 1
3 0 1
3
3 3 1
5 0 1 1 1 2
1 1
2 1 1
4
0 1 1
3 0 1 1 1
3 3 0
0 0 3 1 1 0
3 0 1
3
提示
数据范围
对于所有数据,,,。初始 个串的总长度不超过 。操作 中读入的串总长度不超过 。
保证数据合法。保证存在一个长度不超过 的字符串使得任意时刻那 个串均是它的子串。
- 对于前 的数据,保证 ,初始 个串的总长度不超过 ,操作 3 中读入的串总长度不超过 。
- 对于前 的数据,保证所有的 ,。
- 对于前 的数据,保证数据没有被加密。