#1189908 (Rust) No.3239 Omnibus

• 問題: No.3239 Omnibus
• ユーザー: LyricalMaestro
• 提出日時: 2026-09-21 03:53:17
• 言語: Rust (1.97.1 + proconio + num + itertools + ACL)
• 結果: AC
• 実行時間: 7,854 ms / 10,000 ms
• コード長: 6,357 bytes
• コンパイル時間: 1,039 ms
• コンパイル使用メモリ: 204,608 KB
• 実行使用メモリ: 30,336 KB
• 最終ジャッジ日時: 2026-09-21 03:55:59
• 合計ジャッジ時間: 150,742 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge4_0

ファイルパターン	結果
sample	AC * 1
other	AC * 33

ソースコード

use proconio::input;
use std::collections::HashMap;

fn same_word(s: &Vec<char>, l: usize, a: &Vec<char>) -> bool {
    for j in 0..a.len() {
        if s[l + j] != a[j] {
            return false;
        }
    }
    true
}

fn main() {
    input! {
        n: usize,
        q: usize,
        s_input: String,
    }

    let mut s: Vec<char> = s_input.chars().collect();

    let sqrt_n = (n as f64).sqrt() as usize;
    let block_num = n / sqrt_n + if n % sqrt_n > 0 { 1 } else { 0 };

    let mut block_info_score: Vec<HashMap<String, usize>> =
        vec![HashMap::new(); block_num];
    let mut block_info_count: Vec<HashMap<String, usize>> =
        vec![HashMap::new(); block_num];

    // 初期構築
    for block_index in 0..block_num {
        let start = block_index * sqrt_n;
        let end = n.min((block_index + 1) * sqrt_n);

        if sqrt_n >= 3 {
            for i in start..end {
                let end0 = i + 2;
                if end0 < end {
                    let word: String = s[i..i + 3].iter().collect();

                    *block_info_score[block_index]
                        .entry(word.clone())
                        .or_insert(0) += i + 1;

                    *block_info_count[block_index]
                        .entry(word)
                        .or_insert(0) += 1;
                }
            }
        }
    }

    for _ in 0..q {
        input! {
            query_type: usize,
        }

        if query_type == 1 {
            input! {
                k_input: usize,
                x_input: char,
            }

            let k = k_input - 1;
            s[k] = x_input;

            let block_index = k / sqrt_n;

            block_info_score[block_index].clear();
            block_info_count[block_index].clear();

            let start = block_index * sqrt_n;
            let end = n.min((block_index + 1) * sqrt_n);

            if sqrt_n >= 3 {
                for i in start..end {
                    let end0 = i + 2;

                    if end0 < end {
                        let word: String = s[i..i + 3].iter().collect();

                        *block_info_score[block_index]
                            .entry(word.clone())
                            .or_insert(0) += i + 1;

                        *block_info_count[block_index]
                            .entry(word)
                            .or_insert(0) += 1;
                    }
                }
            }
        } else {
            input! {
                l_input: usize,
                r_input: usize,
                a_input: String,
            }

            let l = l_input - 1;
            let r = r_input - 1;
            let a: Vec<char> = a_input.chars().collect();

            if sqrt_n >= 3 {
                let block_index_l = l / sqrt_n;
                let block_index_r = r / sqrt_n;

                if block_index_l == block_index_r {
                    if r - l + 1 < 3 {
                        println!("0");
                    } else {
                        let mut ans: usize = 0;

                        for i in l..=r {
                            let start = i;
                            let end = i + 2;

                            if l <= start && end <= r {
                                if same_word(&s, i, &a) {
                                    ans += i + 1 - l;
                                }
                            }
                        }

                        println!("{}", ans);
                    }
                } else {
                    let mut ans: usize = 0;

                    // 左端ブロック
                    let left_block_end = (block_index_l + 1) * sqrt_n;

                    for i in l..left_block_end {
                        let start = i;
                        let end = i + 2;

                        if l <= start && end < left_block_end {
                            if same_word(&s, i, &a) {
                                ans += i + 1 - l;
                            }
                        }
                    }

                    // 完全に含まれる中間ブロック
                    for k_index in (block_index_l + 1)..block_index_r {
                        let a_string: String = a.iter().collect();

                        if let Some(&score) = block_info_score[k_index].get(&a_string) {
                            let count = block_info_count[k_index][&a_string];
                            ans += score - l * count;
                        }
                    }

                    // 右端ブロック
                    let end0 = (r + 1).min((block_index_r + 1) * sqrt_n);

                    for i in (block_index_r * sqrt_n)..end0 {
                        let start = i;
                        let end = i + 2;

                        if block_index_r * sqrt_n <= start && end < end0 {
                            if same_word(&s, i, &a) {
                                ans += i + 1 - l;
                            }
                        }
                    }

                    // ブロック境界を跨ぐ3文字列
                    for k_index in (block_index_l + 1)..=block_index_r {
                        for d in [-2isize, -1isize] {
                            let start_signed =
                                (k_index * sqrt_n) as isize + d;

                            if start_signed < 0 {
                                continue;
                            }

                            let start = start_signed as usize;
                            let end = start + 2;

                            if l <= start && end <= r {
                                if same_word(&s, start, &a) {
                                    ans += start + 1 - l;
                                }
                            }
                        }
                    }

                    println!("{}", ans);
                }
            } else {
                let mut ans: usize = 0;

                for i in l..=r {
                    let end = i + 2;

                    if end <= r {
                        if same_word(&s, i, &a) {
                            ans += i + 1 - l;
                        }
                    }
                }

                println!("{}", ans);
            }
        }
    }
}