这个题目的 \(2\) 操作代表着需要维护一个可持久化的东西。
但是因为它没有强制在线，根据常识，可以离线生成一个操作树来降低思考难度。
不难发现最终的字符串的长度可能会非常长，可以达到 \(n\cdot x=10^9\) 级别，这提示我们不能从字符串本身入手。
考虑一个后缀是 Border 需要满足什么条件，假设现在有字符串 \(aa|c|bb|aaa|c|b\)，其中的一个 Border 就是 \(aacb\)。我们把它的对应段拿出来，即 \((a,2)(c,1)(b,2)\) 和 \((a,3)(c,1)(b,1)\)，可以发现的是，它的第一段的长度必须大于等于整个字符串的第一段的长度，它的最后一段的长度必须要小于等于对应段的长度，而中间部分必须完全相同。
所以我们可以考虑把每个操作看成是 \((c_i,x_i)\) ，并且用 KMP 维护这个过程。
首先考虑怎么维护 \(fail\) 数组。需要特别注意的是，因为我们现在使用增量法求答案（树结构的性质使然），所以这里的 \(fail\) 定义为一个最长的后缀，使得该后缀的第一段的长度大于等于整个字符串的第一段的长度，且剩下部分和整个字符串后面部分完全相同。这和一般的 \(fail\) 略微有点区别。
我们现在的操作是一个树结构，而 KMP 暴力找 \(fail\) 的复杂度是均摊的，所以我们在加入一个段的时候并不能直接暴力跳 \(fail\) 指针。考虑设 \(nxt_{now,c,x}\) 表示在节点 \(now\)，加上 \(x\) 的字符 \(c\) 会跳到哪里，可以用主席树维护这个东西，即把 \(nxt_{now,c}\) 看成是一个线段树，每次扫到一个儿子时把 \(nxt_{now,c}\) 从 \(fail_{now}\) 那里继承，假设它到该儿子的边是 \((C,X)\)，那么直接把 \(nxt_{now,C}\) 中的 \(X\) 赋值成这个儿子即可。
需要特别注意的是，我们前面有【Border 的第一段的长度必须大于等于整个串的第一段的长度】，也就是说对于一个串，如果它的 \(fail\) 需要考虑整个串的第一段的时候稍微有点特殊，直接把整个串的第一段看成是 \((c,x\sim 10000)\) 的段即可。
这样我们就动态维护出了 \(fail\) 数组，考虑通过这个来维护答案。
假设现在加入的段是 \((c,x)\)。
把它的 \(fail\) 树上到根的链拿出来，假设是一个这样的结构。其中 \((c,x_i)\) 表示这个点下面有一个 \((c,x_i)\) 的操作。\(length\) 表示整个字符串到它这里的长度。
可以发现对于长度为 \([1,x1]\) 的部分，第 \(i\) 个的 \(nxt\) 长度是 \(length_{fail1}+i\)。对于 \([x1+1,x2]\) 的部分，第 \(i\) 个的\(nxt\) 的长度是 \(length_{fail2}+i\)，以此类推。我们把这个长度给拆开，那么一部分是 \(length\) 的和，一部分是 \(i\) 的和。对于后者，只要求出其 \(fail\) 链上最长的一个 \(x\)，总和就是 \(\frac{x(x+1)}{2}\)。对于前者，可以发现如果一个地方有多个选择，一定选择 \(length\) 最长的一个，而我们整个过程是在树上遍历，每次往下走 \(length\) 是单调不减的，所以可以类似于维护 \(fail\)，用 \(len_{now,c,x}\) 表示这个点 \(now\) 一直往上跳 \(fail\) 树，往下加 \(x\) 的最大 \(length\)，用主席树维护 \(len_{now,c}\)，每次扫的一个儿子时把 \(len_{now,c}\) 从 \(fail_{now}\) 那里继承，假设它到该儿子的边是 \((C,X)\)，那么直接把 \(len_{now,c}\) 中的 \(1\sim X\) 赋值成 \(length_{now}\)。
需要注意的是，如果这个加入的段可以匹配整个串的第一段，如 \(abaa\)，最后的那个 \(a\) 就需要特判。稍加讨论即可。
这样就可以直接做了。时空复杂度 \(O(n\log n)\)。