【HNOI 2019】JOJO

2024-03-04 17:57:59

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

Output

Explanation

Explanation for Sample

操作	此时的串	答案（取模后）
\(1\)	`aa`	\(0+1=1\)
\(2\)	`aabbb`	\(0+1+0+0+0=1\)
\(3\)	`aabbbaa`	\(0+1+0+0+0+1+2=4\)
\(4\)	`aabbbaab`	\(0+1+0+0+0+1+2+3=7\)
\(5\)	`aabbb`	\(0+1+0+0+0=1\)
\(6\)	`aabbbaaa`	\(0+1+0+0+0+1+2+2=6\)
\(7\)	`aabbbaaabb`	\(0+1+0+0+0+1+2+2+3+4=13\)
\(8\)	`aabbbaaa`	\(0+1+0+0+0+1+2+2=6\)
\(9\)	`aabbb`	\(0+1+0+0+0=1\)
\(10\)	`aabbbaaaaaaa`	\(0+1+0+0+0+1+2+2+2+2+2+2=14\)
\(11\)	`aabbbaaaaaaaccccc`	\(0+1+0+0+0+1+2+2+2+2+2+2+0+0+0+0+0=14\)

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\) ，直到当前位置的后一个字符与加入字符相同。

那么由于每次加入的字段都与前面的字符不同，则我们发现，对于一对相同的前后缀，删掉开头结尾的第一个字段，中间的都是完整的字段。那么我们可以将一个字段视作一个新的字符进行 \(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]);
}

码农公寓