#P11740. [集训队互测 2015] ydc 的字符串

[集训队互测 2015] ydc 的字符串

题目描述

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

字符串是由字符组成的。字符一共 mm 种,分别编号为 0,,m10, \dots, m-1

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

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

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

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

输入格式

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

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

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

接下来 nn 行,第 ii 行将给出第 ii 个字符串。

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

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

  • 如果是操作 00,那么接着两个整数 x,cx, c
  • 如果是操作 11,那么接着五个整数 x,y,k,l,rx,y,k,l,r
  • 如果是操作 22,那么接着两个整数 x,yx,y
  • 如果是操作 33,那么接着两个整数 l,rl,r 和一个字符串 ss

输出格式

按照输入顺序回答询问。

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

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

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

提示

数据范围

对于所有数据,2n52 \leq n \leq 51m1051 \leq m \leq 10^51q2×1051 \leq q \leq 2 \times 10^5。初始 nn 个串的总长度不超过 2×105+202 \times 10^5+20。操作 33 中读入的串总长度不超过 10610^6

保证数据合法。保证存在一个长度不超过 4×1054 \times 10^5 的字符串使得任意时刻那 nn 个串均是它的子串。

  • 对于前 30%30\% 的数据,保证 q1000q \leq 1000,初始 nn 个串的总长度不超过 1000+201000+20,操作 3 中读入的串总长度不超过 10410^4
  • 对于前 60%60\% 的数据,保证所有的 l=0l=0r=m1r=m-1
  • 对于前 80%80\% 的数据,保证数据没有被加密。