#PQJ42x4266. QOJ 42_4266

    ID: 2964 传统题 5000ms 512MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:集训队互测 2015字符串AC自动机后缀数组平衡树

QOJ 42_4266

标题: ydc的字符串 - Problem - QOJ.ac

#4266. ydc的字符串

Statistics

The problem was used in the following contests:

ydc 很喜欢字符串,他有特别的视角看待字符串。

字符串是由字符组成的。字符一共 m 种,分别编号为 0,…,m−1。

对于整数 l,r,如果两个字符串 s,t 满足在 s 最前面加一个编号在区间 [l,r] 以内的字符后两串相等,那么就称 s 能通过 [l,r] 与 t 相等。

ydc 将给你 n 个字符串,编号为 1,…,n,并要求进行 q 次操作,每次操作形如以下四种之一:

  • 操作0:在第 x 个字符串后面加上一个字符 c。保证 1≤x≤n,0≤c<m。
  • 操作1:询问当前第 x 个字符串中有多少个子串满足在第 k 个操作过后的第 y 个字符串能通过 [l,r] 与该子串相等。k 是小于当前操作编号的非负整数,k=0 表示在所有操作之前。保证 1≤x,y≤n,0≤l≤r<m。
  • 操作2:将第 x 个字符串改成第 y 个字符串。保证 1≤x,y≤n。
  • 操作3:给你一个字符串 s,对于这 n 个串中的每个串询问有多少个子串满足 s 能通过 [l,r] 与该子串相等,0≤l≤r<m。

另外,输入文件可能被加密来强制你在线进行操作。

输入格式

第一行三个整数数,n,m,ty,分别表示字符串个数,字符集大小,以及是否数据是否被加密。如果数据被加密,则 ty 的值为 1,否则为 0。

如果数据被加密,令 lastans 为当前操作之前最后一个输出的数(如果此前没有输出则 lastans=0)。那么当前操作中读入的所有数均被加密成了原数异或 lastans。

字符串将按照如下格式给出:第一个数为一个正整数 l 表示字符串的长度,后面跟着 l 个整数,两两之间用空格隔开,表示每个位置上的字符编号。

接下来 n 行,第 i 行将给出第 i 个字符串。

再读入一个正整数 q,即操作数。

接着 q 行,每行为一个操作的信息。每行第一个数为操作的类型编号。

如果是操作0,那么接着两个整数 x,c。

如果是操作1,那么接着五个整数 x,y,k,l,r。

如果是操作2,那么接着两个整数 x,y。

如果是操作3,那么接着两个整数 l,r 和一个字符串 s。

输出格式

按照输入顺序回答询问。

对于每个操作1,输出一行一个整数表示答案。

对于每个操作3,输出一行 n 个整数分别表示每个字符串中满足条件的子串个数。

样例一

input

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


output

3 0 1
3


样例二

input

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


output

3 0 1
3


限制与约定

2≤n≤5,1≤m≤105,1≤q≤2×105。

初始 n 个串的总长度不超过 2×105+20。

操作3中读入的串总长度不超过 106。

保证数据合法。

保证存在一个长度不超过 4×105 的字符串使得任意时刻那 n 个串均是它的子串。

对于前 30% 的数据,保证 q≤1000,初始 n 个串的总长度不超过 1000+20,操作3中读入的串总长度不超过 104。

对于前 60% 的数据,保证所有的 l=0,r=m−1。

对于前 80% 的数据,保证数据没有被加密。

**时间限制:**5s

**空间限制:**512MB

来源

中国国家集训队互测2015 - By 刘研绎