クエリを文字列順序でソートし、スタックを \(2\) 本管理しながら走査する方針の解説です。

多重集合 \(X, Y\) の最終的な値を改めて \(X, Y\) と置きます。

目標

\(Y\) に属する各文字列 \(t\) に対して、\(X\) に属する文字列 \(s\) であって、

• \(t\) の prefix である
• そのようなものの中で最も追加時刻が早い

を満たすものの追加時刻を計算すれば、\(t\) が答えに寄与している期間が特定できるため、累積和で答えが計算できます。これを計算しましょう。

方法

簡単のため、クエリで与えられる文字列はすべて相異なることを仮定します。

まずはクエリを文字列でソートしておきます。ソートしたクエリ列を先頭から走査します。その際、現在指している文字列の prefix であるもの全体のなす列を、stack で管理しましょう。これを \(P\)（コード中の pref_stack）と表します。

スタックの更新方法

新しい文字列 \(s\) を訪問する際、\(P\) の先頭が \(s\) の prefix になるまで pop し続け、その後で \(s\) を push すればよいです。

答えの計算方法（スタックの更新後）

\(Y\) に属する新しい文字列 \(t\) を訪問する際、\(P\) 内にある \(X\) に属する文字列のうち訪問時刻が最小のものを特定します。それが答えです。

ところでそれを計算するためには、\(P\) 内にある \(X\) に属する文字列 \(s\) のうち、

• \(P\) 内にある \(X\) に属する文字列はすべて\(X\) より訪問時刻が遅い

を満たすもの全体のなす列を、別のスタック \(D\)（コード中の decr_stack）で管理しておけば、\(D\) の top が答えになっています。

入力例 2 の場合

計算量

\(N = \sum_{i = 1}^Q |S_i|\) と置きます。

• クエリのソートは、 MSD radix ソート、suffix array、trie などにより、\(O(N)\) 時間で実現できます。（オススメ知りたいです。）
• スタック \(P, D\) の操作は \(O(N)\) 時間です。
• スタック \(P\) に出し入れするときの prefixness 判定は、\(P\) の top との LCP length をさえ計算すればよいので合計 \(O(N)\) です。（また、実は毎回計算しても償却するので \(O(N)\) 時間。）
• 累積和の計算も \(O(N)\) 時間です。

以上より、\(O (N)\) 時間、\(O(N)\) 空間になります。

文字列に重複がある場合

\(X\) に属する文字列が、常に \(Y\) に属する文字列より先にくるようにソートすればよいです。

コード

文字列列のソートは MSD radix sorting を用います。なお標準のソートでもほとんど変わらないくらい速かったです。

なお実装上の都合で、\(P, D\) の bottom にはそれぞれ \(q , \infty\) の番兵を入れ、クエリ列の末尾に空文字列クエリを番兵として入れています。

• MSD radis sorting: Rust 209ms
• 標準のソート: Rust 228 ms

use proconio::input;

fn main() {
    input! {
        q: usize,
        mut queries: [(u8, String); q],
    }
    queries.push((u8::MAX, String::new()));
    let mut sorted = (0..q).collect::<Vec<_>>();
    sort_queries(0, &queries, &mut sorted);
    let mut pref_stack = vec![q];
    let mut decr_stack = vec![usize::MAX];
    let mut ans = vec![0; q + 1];
    for &q_id in &sorted {
        while !queries[q_id]
            .1
            .starts_with(&queries[*pref_stack.last().unwrap()].1)
        {
            if *decr_stack.last().unwrap() == pref_stack.pop().unwrap() {
                decr_stack.pop().unwrap();
            }
        }
        pref_stack.push(q_id);
        if queries[q_id].0 == 1 {
            if *decr_stack.last().unwrap() > q_id {
                decr_stack.push(q_id);
            }
        } else {
            ans[q_id] += 1;
            ans[(*decr_stack.last().unwrap()).clamp(q_id, q)] -= 1;
        }
    }
    for i in 1..=q {
        ans[i] += ans[i - 1];
    }
    for &ans in &ans[..q] {
        println!("{ans}");
    }
}

fn sort_queries(depth: usize, queries: &[(u8, String)], sorted: &mut [usize]) {
    let mut buckets = std::array::from_fn::<_, 28, _>(|_| Vec::new());
    for &i in &*sorted {
        if queries[i].1.len() == depth {
            buckets[usize::from(queries[i].0 - 1)].push(i);
        } else {
            let c = queries[i].1.as_bytes()[depth] - b'a';
            buckets[c as usize + 2].push(i);
        }
    }
    let mut start = 0;
    for i in 0..28 {
        let end = start + buckets[i].len();
        sorted[start..end].copy_from_slice(&buckets[i]);
        if 2 <= i && start + 1 < end {
            sort_queries(depth + 1, queries, &mut sorted[start..end]);
        }
        start = end;
    }
}