【HNOI 2019】JOJO

「爱情、让人受尽委屈。」 2023-08-17 15:48 96阅读 0赞

# Problem #

## Description ##

JOJO 的奇幻冒险是一部非常火的漫画。漫画中的男主角经常喜欢连续喊很多的「欧拉」或者「木大」。

为了防止字太多挡住漫画内容，现在打算在新的漫画中用 \\(x\\) 欧拉或者 \\(x\\) 木大表示有 \\(x\\) 个欧拉或者木大。

为了简化内容我们现在用字母表示喊出的话。

我们用数字和字母来表示一个串，例如：`2 a 3 b` 表示的串就是 `aabbb`。

一开始漫画中什么话都没有，接下来你需要依次实现 \\(n\\) 个操作，总共只有 \\(2\\) 种操作：

*  第一种：`1 x c`：在当前漫画中加入 \\(x\\) 个 \\(c\\)，表示在当前串末尾加入 \\(x\\) 个 \\(c\\) 字符。保证当前串是空串或者串尾字符不是 \\(c\\)；
 *  第二种：`2 x`：觉得漫画没画好，将漫画还原到第 \\(x\\) 次操作以后的样子，表示将串复原到第 \\(x\\) 次操作后的样子，如果 \\(x=0\\) 则是将串变成空串。如果当前串是 `bbaabbb`，第 \\(4\\) 次操作后串是 `bb`，则 `2 4` 会使 `bbaabbb` 变成 `bb`，保证 \\(x\\) 小于当前操作数。

众所周知空条承太郎十分聪明，现在迪奥已经被打败了，他开始考虑自己的漫画中的一些问题：

对于一个串的每个前缀 \\(A\\)，都有一个最长的比它短的前缀 \\(B\\) 与前缀 \\(A\\) 的一个后缀匹配，设这个最长的前缀 \\(B\\) 的长度为 \\(L\\)。\\(L\\) 为 \\(0\\) 时意味着 \\(B\\) 是一个空串。

每一次操作后，你都需要将当前的串的所有前缀的 \\(L\\) 求和并对 \\(998244353\\) 取模输出告诉空条承太郎，好和他的白金之星算出的答案对比。比如 `bbaaabba` 的 \\(L\\) 分别是 \\(0, 1, 0, 0, 0, 1, 2, 3\\)，所以对于这个串的答案就是 \\(7\\)

## Input Format ##

第一行包括一个正整数 \\(n\\)，表示操作数量。

接下来 \\(n\\) 行每行包含一个操作，操作格式如题目描述所示，例如：

*  `1 x c`
 *  `2 x`

保证数据合法。

## Output Format ##

仅包含 \\(n\\) 行，第 \\(i\\) 行一个整数，表示 \\(i\\) 个操作之后串的答案。

## Sample ##

### Input ###

11
    1 2 a
    1 3 b
    1 2 a
    1 1 b
    2 2
    1 3 a
    1 2 b
    2 6
    2 5
    1 7 a
    1 5 c

### Output ###

1
    1
    4
    7
    1
    6
    13
    6
    1
    14
    14

## Explanation ##

### Explanation for Sample ###

<table> 
 <thead> 
 <tr> 
 <th style="text-align:center;">操作</th> 
 <th style="text-align:center;">此时的串</th> 
 <th style="text-align:center;">答案（取模后）</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td style="text-align:center;">\(1\)</td> 
 <td style="text-align:center;"><code>aa</code></td> 
 <td style="text-align:center;">\(0+1=1\)</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">\(2\)</td> 
 <td style="text-align:center;"><code>aabbb</code></td> 
 <td style="text-align:center;">\(0+1+0+0+0=1\)</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">\(3\)</td> 
 <td style="text-align:center;"><code>aabbbaa</code></td> 
 <td style="text-align:center;">\(0+1+0+0+0+1+2=4\)</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">\(4\)</td> 
 <td style="text-align:center;"><code>aabbbaab</code></td> 
 <td style="text-align:center;">\(0+1+0+0+0+1+2+3=7\)</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">\(5\)</td> 
 <td style="text-align:center;"><code>aabbb</code></td> 
 <td style="text-align:center;">\(0+1+0+0+0=1\)</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">\(6\)</td> 
 <td style="text-align:center;"><code>aabbbaaa</code></td> 
 <td style="text-align:center;">\(0+1+0+0+0+1+2+2=6\)</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">\(7\)</td> 
 <td style="text-align:center;"><code>aabbbaaabb</code></td> 
 <td style="text-align:center;">\(0+1+0+0+0+1+2+2+3+4=13\)</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">\(8\)</td> 
 <td style="text-align:center;"><code>aabbbaaa</code></td> 
 <td style="text-align:center;">\(0+1+0+0+0+1+2+2=6\)</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">\(9\)</td> 
 <td style="text-align:center;"><code>aabbb</code></td> 
 <td style="text-align:center;">\(0+1+0+0+0=1\)</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">\(10\)</td> 
 <td style="text-align:center;"><code>aabbbaaaaaaa</code></td> 
 <td style="text-align:center;">\(0+1+0+0+0+1+2+2+2+2+2+2=14\)</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">\(11\)</td> 
 <td style="text-align:center;"><code>aabbbaaaaaaaccccc</code></td> 
 <td style="text-align:center;">\(0+1+0+0+0+1+2+2+2+2+2+2+0+0+0+0+0=14\)</td> 
 </tr> 
 </tbody> 
</table>

### Range ###

\\(20\\%\\) 的数据满足 \\(n\\le 300\\)，对于每个 \\(1\\) 操作中的 \\(x\\le 300\\)；

另有 \\(30\\%\\) 的数据满足 \\(n\\le 10^5\\)，且对于每个 \\(1\\) 操作中的 \\(x=1\\)；

另有 \\(30\\%\\) 的数据满足 \\(n\\le 10^5\\)，且不含 \\(2\\) 操作；

\\(100\\%\\) 的数据满足 \\(n\\le 10^5\\)，且每个 \\(1\\) 操作中的 \\(x\\le 10^4\\)。

# Algorithm #

\\(KMP\\) 。

# Mentality #

挺神的一道题。

对于每次第一种操作加入的字符，我们将其看作一个整体，可以称其为字段，一个字段拥有字符与长度两种属性。

先考虑一个 \\(50\\) 分做法（虽然说是 \\(50\\) 分，但本题数据水，实际上可以 \\(A\\) 掉）：当我们在结尾加入一个字符时，回想一下跳 \\(KMP\\) 的过程：不断跳前一位的 \\(nx\\) ，直到当前位置的后一个字符与加入字符相同。

![o\_Say5.png][o_Say5.png]

那么由于每次加入的字段都与前面的字符不同，则我们发现，对于一对相同的前后缀，删掉开头结尾的第一个字段，中间的都是完整的字段。那么我们可以将一个字段视作一个新的字符进行 \\(KMP\\) ，同时特别的，对于第一个字段，我们将所有与它字符相同且长度大于它的字段视作相同字段。

那么每次新加入一个字段，我们只需要不断跳 \\(nx\\) 并计算答案。

虽然此算法能通过此题，但毕竟复杂度不正确，因为 \\(KMP\\) 跳数组的 \\(O(n)\\) 是均摊意义下的，若有回溯操作并刻意构造就能够完美卡掉它。那么考虑令跳 \\(KMP\\) 的过程复杂度正确。

可以考虑一个平时由于复杂度均摊而完全不会考虑的优化：循环节。对于跳 \\(nx\\) ，假设当前在位置 \\(i\\) ，若 \\(nx\_i < \\frac\{i\}\{2\}\\) ，则跳 \\(nx\\) 会使长度减少到一半以下。但如果 \\(nx\_i > \\frac\{i\}\{2\}\\) ，则可能导致长度只会减少一点点，从而复杂度错误。

但是，如果 \\(nx\_i > \\frac\{i\}\{2\}\\) ，它就会产生至少两个循环节！（譬如 \\(ABABA\\) 的形式）那么我们只需要加上一个判断：若当前前缀 \\(i\\) 存在循环节，先判断末尾循环节是否满足要求，然后调试第一个循环节即可。

这样的话每次长度必定缩短一半以上，则跳 \\(KMP\\) 的复杂度上限优化为每次 \\(O(log(n))\\) ，总复杂度 \\(O(nlogn)\\)。

# Code #

#include <algorithm> #include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <map> #include <queue> #include <set> #include <vector> using namespace std; const int Max_n = 1e5 + 5, mod = 998244353; int n; long long Ans[Max_n]; int f[Max_n], l[Max_n], len[Max_n], sum[Max_n]; char P[Max_n], c[Max_n]; int cntr, hd[Max_n], nx[Max_n], to[Max_n]; void addr(int u, int v) { cntr++; nx[cntr] = hd[u], to[cntr] = v; hd[u] = cntr; } void Mod(long long &x) { x %= mod; } void calc(int x, int L, long long ans) { if (len[x]) { if (!L) Mod(ans = (len[x] - 1) * len[x] / 2); int maxx = 0, now = f[L], lastgap = 0; for (int i = f[L]; ~i; i = f[i]) { if (P[i + 1] == c[x] && min(l[i + 1], len[x]) > maxx) { int tp = maxx; maxx = min(l[i + 1], len[x]); Mod(ans += 1ll * (maxx - tp) * sum[i] + (maxx - tp) * (tp + 1 + maxx) / 2); } if (i - f[i] == lastgap && i) i = i % lastgap + lastgap; lastgap = i - f[i]; } if (c[x] == P[1] && L) Mod(ans += (len[x] - maxx) * l[1]); lastgap = 0; f[L + 1] = 0; for (int i = f[L++]; ~i; i = f[i]) { if (P[1] == c[x] && l[1] <= len[x]) f[L] = 1; if (P[i + 1] == c[x] && l[i + 1] == len[x]) { f[L] = i + 1; break; } if (i - f[i] == lastgap && i) i = i % lastgap + lastgap; lastgap = i - f[i]; } P[L] = c[x], sum[L] = sum[L - 1] + (l[L] = len[x]); } Ans[x] = ans; for (int i = hd[x]; i; i = nx[i]) calc(to[i], L, ans); } int main() { #ifndef ONLINE_JUDGE freopen("5287.in", "r", stdin); freopen("5287.out", "w", stdout); #endif scanf("%d", &n); int opt, x; for (int i = 1; i <= n; i++) { scanf("%d%d", &opt, &x); if (opt == 2) { addr(x, i); } else { addr(i - 1, i); scanf(" %c", &c[i]); len[i] = x; } } f[0] = -1; calc(0, 0, 0); for (int i = 1; i <= n; i++) printf("%lld\n", Ans[i]); }

转载于:https://www.cnblogs.com/luoshuitianyi/p/11443617.html

[o_Say5.png]: /images/20230810/f5f6b5b61f764a398ad6e86723df4cf1.png