#P5408. [2018年湖南省队集训]string

    ID: 4420 传统题 1500ms 512MiB 尝试: 110 已通过: 21 难度: 10 上传者: 标签>难度分类省选/NOI-字符串广义后缀自动机endpos 等价类数据结构Link-Cut Tree历史版本查询模拟与实现技巧增量维护CF3000

[2018年湖南省队集训]string

[2018 年湖南省队集训] string

题目描述

给定 nn 个字符串 S1,…,SnS_1,\ldots,S_n,它们都由数字字符组成。需要维护四种操作。

设 Sx(y)S_x^{(y)} 表示第 yy 次操作结束后第 xx 个字符串的内容,Sx(0)S_x^{(0)} 为初始内容。出现次数统计的是子串的所有出现位置,允许相互重叠。

  1. 在当前第 xx 个字符串的末尾追加一个数字字符。
  2. 查询历史字符串 Sx(y)S_x^{(y)} 在当前第 zz 个字符串中出现了多少次。
  3. 查询当前 nn 个字符串一共含有多少种不同的非空子串。内容相同的子串只算一种。
  4. 给定一个字符串 TT,求 TT 在任意一个当前字符串中的最大出现次数。

输入格式

第一行两个整数 n,tn,t。t=1t=1 表示强制在线,t=0t=0 表示直接使用输入。

接下来 nn 行,每行一个初始字符串。

下一行一个整数 mm,表示操作数。

接下来 mm 行,每行按以下格式之一给出。

  • 1 x y:在第 xx 个字符串末尾追加一个字符。t=0t=0 时追加数字 yy。t=1t=1 时,追加的数字为 (yxor⁡lastans) mod 10(y\operatorname{xor}lastans)\bmod 10,其中 xor⁡\operatorname{xor} 为按位异或。
  • 2 x y z:查询 Sx(y)S_x^{(y)} 在当前第 zz 个字符串中的出现次数。
  • 3:查询当前所有字符串中不同的非空子串个数。
  • 4 T:查询 TT 在任意一个当前字符串中的最大出现次数。

lastanslastans 初始为 00,随后取最近一次操作 22 或 44 的答案。操作 33 的答案不影响 lastanslastans。

输出格式

对每个操作 22、33 或 44,输出一行一个整数,表示答案。

样例

3 0
121
123
1
4
1 3 2
3
2 3 0 1
4 12
8
2
1

第一次查询时,不同的非空子串为 1、2、12、21、121、3、23、123,共 88 种。

第二次查询中,初始的第三个字符串 1 在 121 中出现两次。第三次查询中,12 在当前三个字符串中各出现一次,故最大次数为 11。

数据范围

用 QQ 表示操作数 mm。∑∣Si∣\sum|S_i| 为初始字符串总长,∑∣T∣\sum|T| 为操作 44 中各查询字符串的总长。

数据比例 限制
20%20\% n≤10n\le10,Q≤100Q\le100,∑∣Si∣≤200\sum\lvert S_i\rvert\le200,∑∣T∣≤1000\sum\lvert T\rvert\le1000
另外 20%20\% 不包含操作 22
另外 30%30\% t=0t=0
100%100\% n≤20n\le20,Q≤2⋅105Q\le2\cdot10^5,∑∣Si∣≤2⋅105\sum\lvert S_i\rvert\le2\cdot10^5,∑∣T∣≤2⋅107\sum\lvert T\rvert\le2\cdot10^7