No.2020 Sum of Common Prefix Length
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 29
作問者 :
souta-1326
/ テスター :
MtSaka
タグ : / 解いたユーザー数 29
作問者 :
souta-1326
/ テスター :
MtSaka
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。