#P2787. Spoj 11482. Count on a trie

    ID: 1895 传统题 1000ms 512MiB 尝试: 88 已通过: 15 难度: 10 上传者: 标签>CF2900省选/NOI-Trie倍增基数排序树上倍增长链剖分二分查找离线查询深度优先搜索树状数组

Spoj 11482. Count on a trie

题目描述

维护两个字符串集合 S,TS,T,一开始 SS 和 TT 里都只有一个空串,编号都为 11,要求支持操作:

  • 1 i c ,在 SiS_i 的末尾加入一个字符 cc,加入 SS。
  • 2 0 i c ,在 TiT_i 的开头加入一个字符 cc,加入 TT。
  • 2 1 i c,在 TiT_i 的末尾加入一个字符 cc,加入 TT。
  • 3 i j ,把 TiT_i 和 TjT_j 拼起来,加入 TT。
  • 4 i j,询问 TiT_i 在 SjS_j 中的出现次数,如果其中任意一个串是空串,那么答案是 00。

输入格式

第一行一个整数 qq,表示操作次数。 接下来每行一个操作,格式见题目描述。

输出格式

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

18
1 1 a
1 2 a
1 3 b
1 2 b
1 5 a
1 5 b
2 1 1 a
3 2 2
2 0 3 b
2 1 2 b
3 2 5
3 5 2
4 7 6
4 5 6
4 3 4
4 2 4
4 2 7
4 2 6
1
1
1
2
1
2

数据规模与约定

对于 100%100\% 的数据,1≤q≤3×1051\leq q\leq 3\times 10^5,cc 是小写字母,11 操作个数不超过 10510^5,33 操作个数不超过 3×1043\times 10^4,44 操作个数不超过 10510^5。