UOJ Logo Universal Online Judge

UOJ

#101. 【集训队互测2015】ydc的字符串

附件下载 统计

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

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

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

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

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

限制与约定

2n51m1051q2×105

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

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

保证数据合法。

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

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

对于前 60% 的数据,保证所有的 l=0r=m1

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

时间限制:5s

空间限制:512MB

来源

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

下载

样例数据下载