UOJ Logo Universal Online Judge

UOJ

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

统计

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

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

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

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

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

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

输入格式

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

如果数据被加密,令 $\mathrm{lastans}$ 为当前操作之前最后一个输出的数(如果此前没有输出则 $\mathrm{lastans} = 0$)。那么当前操作中读入的所有数均被加密成了原数异或 $\mathrm{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 \leq n \leq 5$,$1 \leq m \leq 10^5$,$1 \leq q \leq 2 \times 10^5$。

初始 $n$ 个串的总长度不超过 $2 \times 10^5+20$。

操作3中读入的串总长度不超过 $10^6$。

保证数据合法。

保证存在一个长度不超过 $4 \times 10^5$ 的字符串使得任意时刻那 $n$ 个串均是它的子串。

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

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

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

时间限制:$5\texttt{s}$

空间限制:$512\texttt{MB}$

来源

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

下载

样例数据下载