[校内训练20161216] T2 版本管理git

时间限制：2000MS      内存限制：1048576KB

难度：\(7.0\)

• 题目描述

在工程的开发中，我们常常用 \(Git\) 进行版本的管理。这个方式具体来说是这样的：刚开始只有一个版本 \(0\)，表示最初始的情况，也就是空的项目；接下来一个用户可以对某一个版本 \(p\) 的项目进行修改，得到一个新的版本 \(i\)。这样，一个工程就产生了许多不同的版本，而管理员可以选择一些优秀的，将其合并到主版本中。

\(F\) 公司有一个项目 \(U\)，这个项目由一个字符串构成。版本 \(0\) 为空串。有 \(n\) 个开发者按顺序对这个项目进行了修改，其中第 \(i\) 个开发者将第 \(p_i ( 0 \le p_i < i)\) 个版本的开头添加上一个字符 \(c_i (1 \le c_i \le m)\) 作为新的版本 \(i\)。

作为项目的总负责人，你希望对这些版本进行评价。对一个字符串 \(S\)，称串 \(S\) 是串 \(T\) 的超前缀，当且仅当串 \(S\) 是串 \(T^{*}\) 的前缀。 \(T^{*}\) 表示 \(T\) 重复无限次得到的一个无限长度的串，如若 \(T = abcd\)，则 \(T^{*} = abcdabcdabcd \cdots\)。我们称串 \(S\) 的 “\(kitty\) 长度” 为 \(l\)，当且仅当存在一个长度为 \(l\) 的串 \(T\) 使得 \(S\) 是 \(T\) 的超前缀，且不存在小于 \(l\) 的串 \(T’\) 使得 \(S\) 是 \(T’\) 的超前缀（定义空串的 \(kitty\) 长度为 \(0\)）。你需要做的就是对每一个版本求出其的 \(kitty\) 长度（设版本 \(i\) 的 \(kitty\) 长度为 \(kitty(i)\)）。

在实际运营中，有两种情况，我们用一个数 \(k \in \{0,1\}\) 表示。在 \(k = 0\) 的情况中， 你可以等候开发者进行所有修改后，再进行计算；但在 \(k = 1\) 的情况中，开发者希望能够实时得到自己修改得到的版本的 \(kitty\) 长度，你需要实时计算出每个版本的 \(kitty\) 长度。

• 输入格式

第一行包含三个整数 \(n,m,k\)。

接下来 \(n\) 行，其中第 \(i\) 行包含两个整数 \(p^{′}_{i}; c^{′}_{i}\)，其中：

如果 \(k = 0\) ，则 \(p_i = p^{′}_{i}\)，\(c_i = c^{′}_{i}\)；

如果 \(k = 1\)，则 \(p_i = p^{′}_{i} \oplus kitty(i – 1)\)，\(c_i = c^{′}_{i} \oplus kitty(i – 1)\)，其中 \(oplus\) 表示按位异或运算。

• 输出格式

\(n\) 行，第 \(i\) 行为 \(kitty(i)\)。

• 样例输入

• 样例输出

• 数据规模与约定

 

 

 

---

 

 

 

不难发现这是一个树上KMP算法，一个串的答案就是它的长度减去它在树链上的最长公共前后缀的长度。

于是可以跟普通KMP一样，当失配的时候往回跳 next 数组，直到相等…………

很显然这样时间复杂度会爆炸，所以考虑使用一个数据结构维护 next 数组。

注意到不同字符数 \(m\) 只有 \(500000\) ，所以可以使用可持久化线段树维护：某个节点所在链上最后一个字符 \(i\) 出现的节点。

和普通KMP一样，加入一个新字符时，找到链上和它字符相同的最后一个节点，复制它的 next 数组（可持久化），最后加入倍增（保证在同一条链上）跳到的它的儿子节点的信息即可。