問題一覧 > 通常問題

No.2020 Sum of Common Prefix Length

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 28
作問者 : souta-1326souta-1326 / テスター : MtSakaMtSaka
2 ProblemId : 8010 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-07-22 20:38:18

注意

この問題では、想定解がPython3でTLEとなり、PyPy3でも十分な高速化をしないと厳しいです( $867\mathrm{ms}$ )。
C++等の高速な言語の使用を推奨します。

問題文

$N$ 個の文字列が与えられ、$i$ 番目の文字列を $S_i$ とします。
$Q$ 個のクエリを順番に処理してください。クエリは次の $2$ 種類のいずれかです。

  • 1 x c: $S_x$ の末尾に文字 $c$ を追加する。
  • 2 x: 各 $k\ (1 \leq k \leq N)$ について $S_x,S_k$ の最長共通接頭辞の長さを求め、それらの総和を答える。

入力

$N$
$S_1$
$S_2$
$\vdots$
$S_N$
$Q$
$\mathrm{query}_1$
$\mathrm{query}_2$
$\vdots$
$\mathrm{query}_Q$
各クエリは次のいずれかの形で与えられます。
$1\ \ x\ \ c$
$2\ \ x$

  • $1 \leq N,Q \leq 2\times 10^5$
  • $N,Q$ は整数
  • $S_i$ は英小文字から成る $1$ 文字以上の文字列
  • $\displaystyle \sum_{i=1}^N |S_i| \leq 2\times 10^5$ (クエリ処理前)
  • $1 \leq x \leq N$
  • $c$ は英小文字
  • $2$ 種類目のクエリが $1$ つ以上存在する

出力

全ての $2$ 種類目のクエリに対して、順番に答えを出力し改行してください。

サンプル

サンプル1
入力
3
a
abc
abcde
4
1 1 b
2 2
1 2 d
2 3
出力
8
11

はじめ、$S = (\mathrm{a,abc,abcde})$ です。
$1$ つ目のクエリでは、$S_1$ の末尾に $\mathrm{b}$ を追加し、 $S_1 = \mathrm{ab}$ となります。
$2$ つ目のクエリでは、$S_2$ と各文字列との最長共通接頭辞の長さの総和を出力します。ここでは、$2+3+3=8$ を出力します。
$3$ つ目のクエリでは、$S_2$ の末尾に $\mathrm{d}$ を追加し、 $S_2 = \mathrm{abcd}$ となります。
$4$ つ目のクエリでは、$S_3$ と各文字列との最長共通接頭辞の長さの総和を出力します。ここでは、$2+4+5=11$ を出力します。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。