#1190676 (Rust) No.3637 PANDORA

• 問題: No.3637 PANDORA
• ユーザー: 👑 cologne
• 提出日時: 2026-09-28 13:12:09
• 言語: Rust (1.97.1 + proconio + num + itertools + ACL)
• 結果: AC
• 実行時間: 386 ms / 2,000 ms
• コード長: 4,011 bytes
• コンパイル時間: 4,196 ms
• コンパイル使用メモリ: 202,308 KB
• 実行使用メモリ: 9,868 KB
• 最終ジャッジ日時: 2026-09-28 13:38:55
• 合計ジャッジ時間: 9,666 ms
• ジャッジサーバーID （参考情報）: judge4_1 / judge1_0

サブタスク	配点	結果
サンプル	0 %	AC * 2
小課題1	5 %	AC * 4
小課題2	10 %	AC * 4
小課題3	5 %	AC * 8
小課題4	10 %	AC * 5
小課題5	20 %	AC * 10
小課題6	20 %	AC * 16
小課題7	30 %	AC * 38
合計	100 点

ソースコード

use fio::*;

fn main() {
    let [n, q] = read_tuple::<usize, 2>();
    let mut s = read_line().bytes().collect::<Vec<_>>();
    let mut bs = vec![vec![0u64; n.div_ceil(64)]; 26];
    for (i, c) in s.iter().enumerate() {
        let a = &mut bs[(c - b'a') as usize];
        a[i / 64] |= 1 << (i % 64);
    }

    for _ in 0..q {
        let q = read_vec::<String>();
        match q[0].as_str() {
            "1" => {
                let i = q[1].parse::<usize>().unwrap() - 1;
                let c = q[2].bytes().next().unwrap();
                let pc = s[i];
                let a = &mut bs[(pc - b'a') as usize];
                a[i / 64] &= !(1 << (i % 64));
                let a = &mut bs[(c - b'a') as usize];
                a[i / 64] |= 1 << (i % 64);
                s[i] = c;
            }
            "2" => {
                let mut idx = Some(0usize);
                let calc = |x: &[u64], st: usize| -> Option<usize> {
                    if st % 64 != 0 {
                        let cur = x[st / 64] & !((1 << (st % 64)) - 1);
                        let tz = cur.trailing_zeros();
                        if tz != 64 {
                            return Some((st / 64) * 64 + (tz as usize) + 1);
                        }
                    }
                    for i in st.div_ceil(64)..x.len() {
                        let tz = x[i].trailing_zeros();
                        if tz != 64 {
                            return Some((i * 64) + (tz as usize) + 1);
                        }
                    }
                    return None;
                };
                for c in q[1].bytes() {
                    idx = idx.and_then(|x| calc(&bs[(c - b'a') as usize], x));
                }
                println!("{}", if idx.is_some() { "Yes" } else { "No" });
            }
            _ => panic!(),
        }
    }
}

mod fio {
    use std::{
        cell::RefCell,
        convert::TryInto,
        fmt::Debug,
        io::{BufRead, BufWriter, StdinLock, StdoutLock, stdin, stdout},
        str::FromStr,
    };
    thread_local! {
        pub static STDIN: RefCell<StdinLock<'static>> = RefCell::new(stdin().lock());
        pub static STDOUT: RefCell<BufWriter<StdoutLock<'static>>> = RefCell::new(BufWriter::new(stdout().lock()));
    }

    #[allow(dead_code)]
    pub fn read<T: FromStr>() -> T
    where
        <T as FromStr>::Err: Debug,
    {
        read_line().parse().unwrap()
    }

    /// If there is a performance concern, use direct
    /// `read_line().spilt_ascii_whitespace().map(|x| x.parse().unwrap())`
    #[allow(dead_code)]
    pub fn read_vec<T: FromStr>() -> Vec<T>
    where
        <T as FromStr>::Err: Debug,
    {
        read_line()
            .split_ascii_whitespace()
            .map(|x| x.parse().unwrap())
            .collect()
    }

    /// If there is a performance concern, use direct
    /// `read_line().spilt_ascii_whitespace().map(|x| x.parse().unwrap())`
    #[allow(dead_code)]
    pub fn read_tuple<T, const N: usize>() -> [T; N]
    where
        T: FromStr + Debug,
        <T as FromStr>::Err: Debug,
    {
        read_vec::<T>().try_into().unwrap()
    }

    /// whitespace at the end of the line is ignored
    pub fn read_line() -> String {
        let mut s = String::new();
        STDIN.with(|cell| {
            cell.borrow_mut().read_line(&mut s).unwrap();
        });
        String::from_str(s.trim_end()).unwrap()
    }
}

#[macro_export]
macro_rules! print {
    ($($t:tt)*) => {
        fio::STDOUT.with(|cell|{
            use std::io::Write;
            write!(cell.borrow_mut(), $($t)*).unwrap()
        })};
}

#[macro_export]
macro_rules! println {
    ($($t:tt)*) => {
        fio::STDOUT.with(|cell| {
            use std::io::Write;
            writeln!(cell.borrow_mut(), $($t)*).unwrap()
        })
    };
}

#[macro_export]
macro_rules! flush {
    () => {
        fio::STDOUT.with(|cell| {
            use std::io::Write;
            cell.borrow_mut().flush().unwrap()
        });
    };
}