#P3881. [Coci2015]Divljak

    ID: 3083 传统题 4000ms 512MiB 尝试: 1379 已通过: 259 难度: 8 上传者: 标签>CF2500省选/NOI-AC 自动机fail 树统计DFS 序排序LCA树上差分树链剖分子树转区间树状数组

[Coci2015]Divljak

题目描述

Alice 有 nn 个字符串 S1,S2...SnS_1,S_2...S_n,Bob 有一个字符串集合 TT,一开始集合是空的。

接下来会发生 qq 个操作,操作有两种形式:

  1. 1 P,Bob 往自己的集合里添加了一个字符串 PP。
  2. 2 x,Alice 询问 Bob,集合 TT 中有多少个字符串包含串 SxS_x。(我们称串 AA 包含串 BB,当且仅当 BB 是 AA 的子串)

Bob 遇到了困难,需要你的帮助。

输入格式

第一行,一个数 nn。

接下来 nn 行,每行一个字符串表示 SiS_i。

下一行,一个数 qq。

接下来 qq 行,每行一个操作,格式见题目描述。

输出格式

对于每一个 Alice 的询问,帮 Bob 输出答案。

3
a
bc
abc
5
1 abca
2 1
1 bca
2 2
2 3
1
2
1

数据规模与约定

对于 100%100\% 的数据,1≤n,q≤1051 \le n,q \le 10^5。

Alice 和 Bob 拥有的字符串长度之和各自都不会超过 2×1062\times 10^6。

字符串都由小写英文字母组成。

题目来源

鸣谢 Dzy