結果

問題 No.2761 Substitute and Search
ユーザー CoCo_Japan_panCoCo_Japan_pan
提出日時 2024-05-17 23:05:56
言語 Rust
(1.77.0)
結果
AC  
実行時間 1,382 ms / 4,000 ms
コード長 13,307 bytes
コンパイル時間 14,788 ms
コンパイル使用メモリ 399,960 KB
実行使用メモリ 115,860 KB
最終ジャッジ日時 2024-05-17 23:06:24
合計ジャッジ時間 26,652 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 1 ms
6,944 KB
testcase_02 AC 1 ms
6,940 KB
testcase_03 AC 1 ms
6,944 KB
testcase_04 AC 733 ms
115,860 KB
testcase_05 AC 1,148 ms
104,320 KB
testcase_06 AC 257 ms
104,320 KB
testcase_07 AC 1,382 ms
110,088 KB
testcase_08 AC 214 ms
104,320 KB
testcase_09 AC 1,263 ms
110,196 KB
testcase_10 AC 218 ms
104,320 KB
testcase_11 AC 1,271 ms
110,208 KB
testcase_12 AC 755 ms
107,236 KB
testcase_13 AC 762 ms
107,376 KB
testcase_14 AC 781 ms
107,192 KB
testcase_15 AC 761 ms
107,344 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#![allow(unused_imports)]
#![allow(unused_macros)]
#![allow(non_snake_case)]

pub use __cargo_equip::prelude::*;

use algebra::{Commutative, Map};
use dual_segtree::DualSegTree;
use modint_mersenne::ModIntMersenne;
use proconio::marker::{Bytes, Chars, Isize1, Usize1};
use proconio::{fastout, input, input_interactive};
use rolling_hash::RollingHash;

#[derive(Clone, Copy, PartialEq, Eq, Debug)]
struct AddMap {
    val: ModIntMersenne,
}
impl Map for AddMap {
    type Target = ModIntMersenne;
    fn id_map() -> Self {
        Self {
            val: ModIntMersenne::new(0),
        }
    }
    fn composition(&mut self, rhs: &Self) {
        self.val += rhs.val;
    }
    fn mapping(&self, target: &mut Self::Target) {
        *target += self.val;
    }
}
impl Commutative for AddMap {}

#[fastout]
fn main() {
    input! {
        N: usize,
        L: usize,
        Q: usize,
        mut S: [Chars; N],
    }
    let base = ModIntMersenne::new(RollingHash::get_random_base());
    let mut dual_segs = {
        let mut ret = Vec::with_capacity(N);
        for i in 0..N {
            ret.push(DualSegTree::<AddMap>::new(S[i].len()))
        }
        ret
    };
    let base_pows = {
        let mut ret = vec![ModIntMersenne::new(1); L + 1];
        for i in 1..=L {
            ret[i] = ret[i - 1] * base;
        }
        ret
    };
    let intial_hashs = {
        let mut ret = Vec::with_capacity(N);
        for s in &S {
            let mut num = vec![ModIntMersenne::new(0); s.len()];
            num[0] = ModIntMersenne::new(s[0] as u32);
            for i in 1..s.len() {
                num[i] = num[i - 1] + ModIntMersenne::new(s[i] as u32) * base_pows[i];
            }
            ret.push(num);
        }
        ret
    };
    for _ in 0..Q {
        input! {
            query_type: usize,
        }
        if query_type == 1 {
            input! {
                k: Usize1,
                c: char,
                d: char,
            }
            for (i, s) in S.iter_mut().enumerate() {
                if s[k] == c {
                    dual_segs[i].apply_commutative(
                        k..,
                        &AddMap {
                            val: base_pows[k]
                                * (ModIntMersenne::new(d as u32) - ModIntMersenne::new(c as u32)),
                        },
                    );
                    s[k] = d;
                }
            }
        } else {
            input! {
                t: Chars,
            }
            let t_hash = {
                let mut ret = ModIntMersenne::new(0);
                for i in 0..t.len() {
                    ret += base_pows[i] * ModIntMersenne::new(t[i] as u32);
                }
                ret
            };
            let ans = (0..N)
                .filter(|&i| {
                    let str_hash =
                        dual_segs[i].get_mapped(t.len() - 1, intial_hashs[i][t.len() - 1]);
                    str_hash == t_hash
                })
                .count();
            println!("{}", ans);
        }
    }
}

#[macro_export]
macro_rules! mat {
    ($($e:expr),*) => { vec![$($e),*] };
    ($($e:expr,)*) => { vec![$($e),*] };
    ($e:expr; $d:expr) => { vec![$e; $d] };
    ($e:expr; $d:expr $(; $ds:expr)+) => { vec![mat![$e $(; $ds)*]; $d] };
}

#[macro_export]
macro_rules! chmin {
    ($a:expr, $b:expr) => {
        if $a > $b {
            $a = $b;
            true
        } else {
            false
        }
    };
}

#[macro_export]
macro_rules! chmax {
    ($a:expr, $b:expr) => {
        if $a < $b {
            $a = $b;
            true
        } else {
            false
        }
    };
}

/// https://maguro.dev/debug-macro/
#[macro_export]
macro_rules! debug {
    ($($a:expr),* $(,)*) => {
        #[cfg(debug_assertions)]
        eprintln!(concat!($("| ", stringify!($a), "={:?} "),*, "|"), $(&$a),*);
    };
}

// The following code was expanded by `cargo-equip`.

///  # Bundled libraries
/// 
///  - `algebra 0.1.0 (git+ssh://git@github.com/CoCo-Japan-pan/procon_lib_rs.git#9ca5e81381d9bc5fe520ed7dcb27065a5cd5825b)`         licensed under `CC0-1.0` as `crate::__cargo_equip::crates::algebra`
///  - `dual_segtree 0.1.0 (git+ssh://git@github.com/CoCo-Japan-pan/procon_lib_rs.git#9ca5e81381d9bc5fe520ed7dcb27065a5cd5825b)`    licensed under `CC0-1.0` as `crate::__cargo_equip::crates::dual_segtree`
///  - `modint_mersenne 0.1.0 (git+ssh://git@github.com/CoCo-Japan-pan/procon_lib_rs.git#9ca5e81381d9bc5fe520ed7dcb27065a5cd5825b)` licensed under `CC0-1.0` as `crate::__cargo_equip::crates::modint_mersenne`
///  - `rolling_hash 0.1.0 (git+ssh://git@github.com/CoCo-Japan-pan/procon_lib_rs.git#9ca5e81381d9bc5fe520ed7dcb27065a5cd5825b)`    licensed under `CC0-1.0` as `crate::__cargo_equip::crates::rolling_hash`
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
    pub(crate) mod crates {
        pub mod algebra {use std::fmt::Debug;pub trait Commutative{}pub trait NonCommutative{}pub trait Map:Clone{type Target:Clone;fn id_map()->Self;fn composition(&mut self,rhs:&Self);fn mapping(&self,target:&mut Self::Target);}pub trait Monoid{type Target:Debug+Clone+Eq;fn id_element()->Self::Target;fn binary_operation(a:&Self::Target,b:&Self::Target)->Self::Target;}pub trait MapMonoid{type Monoid:Monoid;type Map:Map<Target=<Self::Monoid as Monoid>::Target>;fn id_element()-><Self::Monoid as Monoid>::Target{Self::Monoid::id_element()}fn binary_operation(a:&<Self::Monoid as Monoid>::Target,b:&<Self::Monoid as Monoid>::Target,)-><Self::Monoid as Monoid>::Target{Self::Monoid::binary_operation(a,b)}fn id_map()->Self::Map{Self::Map::id_map()}fn composition(f:&mut Self::Map,g:&Self::Map){f.composition(g)}fn mapping(x:&mut<Self::Monoid as Monoid>::Target,f:&Self::Map){f.mapping(x)}}pub trait IdempotentMonoid:Monoid{}pub trait Group:Monoid{fn inverse(a:&Self::Target)->Self::Target;}pub trait Semiring:Debug+Clone+Eq{type Target:Debug+Clone+Eq;fn zero()->Self::Target;fn one()->Self::Target;fn add_assign(a:&mut Self::Target,b:&Self::Target);fn mul(a:&Self::Target,b:&Self::Target)->Self::Target;}}
        pub mod dual_segtree {use crate::__cargo_equip::preludes::dual_segtree::*;use algebra::{Commutative,Map,NonCommutative};use std::ops::RangeBounds;#[derive(Debug)]pub struct DualSegTree<T:Map>{range_size:usize,leaf_size:usize,log:usize,lazy_nodes:Vec<T>,}impl<T:Map>DualSegTree<T>{pub fn new(size:usize)->Self{let mut leaf_size=1;let mut log=0;while leaf_size<size{leaf_size*=2;log+=1;}Self{range_size:size,leaf_size,log,lazy_nodes:vec![T::id_map();2*leaf_size],}}pub fn get_mapped(&self,i:usize,mut target:T::Target)->T::Target{assert!(i<self.range_size);let mut i=i+self.leaf_size;while i>0{self.lazy_nodes[i].mapping(&mut target);i>>=1;}target}pub fn get_composition(&self,i:usize)->T{assert!(i<self.range_size);let mut i=i+self.leaf_size;let mut res=T::id_map();while i>0{res.composition(&self.lazy_nodes[i]);i>>=1;}res}}impl<T:Map+Commutative>DualSegTree<T>{pub fn apply_commutative<R:RangeBounds<usize>>(&mut self,range:R,map:&T){let mut l=match range.start_bound(){std::ops::Bound::Included(&l)=>l,std::ops::Bound::Excluded(&l)=>l+1,std::ops::Bound::Unbounded=>0,};let mut r=match range.end_bound(){std::ops::Bound::Included(&r)=>r+1,std::ops::Bound::Excluded(&r)=>r,std::ops::Bound::Unbounded=>self.range_size,};assert!(l<=r&&r<=self.range_size);if l==r{return;}l+=self.leaf_size;r+=self.leaf_size;while l<r{if l&1==1{self.lazy_nodes[l].composition(map);l+=1;}if r&1==1{r-=1;self.lazy_nodes[r].composition(map);}l>>=1;r>>=1;}}}impl<T:Map+NonCommutative>DualSegTree<T>{pub fn apply_non_commutative<R:RangeBounds<usize>>(&mut self,range:R,map:&T){let mut l=match range.start_bound(){std::ops::Bound::Included(&l)=>l,std::ops::Bound::Excluded(&l)=>l+1,std::ops::Bound::Unbounded=>0,};let mut r=match range.end_bound(){std::ops::Bound::Included(&r)=>r+1,std::ops::Bound::Excluded(&r)=>r,std::ops::Bound::Unbounded=>self.range_size,};assert!(l<=r&&r<=self.range_size);if l==r{return;}l+=self.leaf_size;r+=self.leaf_size;for i in(1..=self.log).rev(){if((l>>i)<<i)!=l{self.propagate(l>>i);}if((r>>i)<<i)!=r{self.propagate((r-1)>>i);}}while l<r{if l&1==1{self.lazy_nodes[l].composition(map);l+=1;}if r&1==1{r-=1;self.lazy_nodes[r].composition(map);}l>>=1;r>>=1;}}fn propagate(&mut self,i:usize){let mut parent=T::id_map();std::mem::swap(&mut parent,&mut self.lazy_nodes[i]);self.lazy_nodes[i*2].composition(&parent);self.lazy_nodes[i*2+1].composition(&parent);}}}
        pub mod modint_mersenne {use std::fmt::Display;use std::ops::{Add,AddAssign,Mul,MulAssign,Neg,Sub,SubAssign};const MOD:u64=(1<<61)-1;#[derive(Debug,Clone,Copy,PartialEq,Eq,Hash)]pub struct ModIntMersenne{value:u64,}impl Display for ModIntMersenne{fn fmt(&self,f:&mut std::fmt::Formatter<'_>)->std::fmt::Result{write!(f,"{}",self.value)}}impl ModIntMersenne{pub fn new<T:RemEuclidU64>(x:T)->Self{x.rem_euclid_u64()}pub fn value(&self)->u64{self.value}pub fn modulus()->u64{MOD}#[inline]fn calc_mod(x:u64)->u64{let tmp=(x>>61)+(x&MOD);if tmp>=MOD{tmp-MOD}else{tmp}}#[inline]fn mul(a:u64,b:u64)->u64{let au=a>>31;let ad=a&((1<<31)-1);let bu=b>>31;let bd=b&((1<<31)-1);let mid=ad*bu+au*bd;let midu=mid>>30;let midd=mid&((1<<30)-1);Self::calc_mod(au*bu*2+midu+(midd<<31)+ad*bd)}}pub trait RemEuclidU64{fn rem_euclid_u64(self)->ModIntMersenne;}impl RemEuclidU64 for u32{fn rem_euclid_u64(self)->ModIntMersenne{ModIntMersenne{value:self as u64}}}impl RemEuclidU64 for u64{fn rem_euclid_u64(self)->ModIntMersenne{ModIntMersenne{value:ModIntMersenne::calc_mod(self),}}}impl RemEuclidU64 for usize{fn rem_euclid_u64(self)->ModIntMersenne{let casted:u64=self.try_into().unwrap();casted.rem_euclid_u64()}}impl RemEuclidU64 for i32{fn rem_euclid_u64(self)->ModIntMersenne{if self<0{-(self.unsigned_abs().rem_euclid_u64())}else{(self as u64).rem_euclid_u64()}}}impl RemEuclidU64 for i64{fn rem_euclid_u64(self)->ModIntMersenne{if self<0{-(self.unsigned_abs().rem_euclid_u64())}else{(self as u64).rem_euclid_u64()}}}impl RemEuclidU64 for isize{fn rem_euclid_u64(self)->ModIntMersenne{let casted:i64=self.try_into().unwrap();casted.rem_euclid_u64()}}impl Neg for ModIntMersenne{type Output=Self;fn neg(self)->Self{if self.value==0{self}else{ModIntMersenne{value:MOD-self.value,}}}}impl AddAssign for ModIntMersenne{fn add_assign(&mut self,rhs:Self){self.value+=rhs.value;if self.value>=MOD{self.value-=MOD;}}}impl Add for ModIntMersenne{type Output=Self;fn add(mut self,rhs:Self)->Self{self+=rhs;self}}impl SubAssign for ModIntMersenne{fn sub_assign(&mut self,rhs:Self){if self.value<rhs.value{self.value+=MOD;}self.value-=rhs.value;}}impl Sub for ModIntMersenne{type Output=Self;fn sub(mut self,rhs:Self)->Self{self-=rhs;self}}impl MulAssign for ModIntMersenne{fn mul_assign(&mut self,rhs:Self){self.value=Self::mul(self.value,rhs.value);}}impl Mul for ModIntMersenne{type Output=Self;fn mul(mut self,rhs:Self)->Self{self*=rhs;self}}}
        pub mod rolling_hash {use crate::__cargo_equip::preludes::rolling_hash::*;use modint_mersenne::ModIntMersenne;use std::iter::once;use std::ops::RangeBounds;use std::time::SystemTime;#[derive(Debug,Clone,PartialEq,Eq)]pub struct RollingHash{len:usize,base_pow_table:Vec<ModIntMersenne>,prefix_hash_table:Vec<ModIntMersenne>,}impl RollingHash{pub fn get_random_base()->u64{let rand_duration=SystemTime::now().duration_since(SystemTime::UNIX_EPOCH).unwrap();rand_duration.subsec_nanos()as u64+rand_duration.as_secs()}pub fn new<T:Into<u64>+Copy>(s:&[T],base:Option<u64>)->Self{let base=if let Some(base)=base{assert!(base>1&&base<ModIntMersenne::modulus()-1);base}else{Self::get_random_base()};let base=ModIntMersenne::new(base);let base_pow_table:Vec<ModIntMersenne> =once(ModIntMersenne::new(1)).chain((0..s.len()).scan(ModIntMersenne::new(1),|acc,_|{*acc*=base;Some(*acc)})).collect();let prefix_hash_table:Vec<ModIntMersenne> =once(ModIntMersenne::new(0)).chain(s.iter().scan(ModIntMersenne::new(0),|acc,s|{*acc=*acc*base+ModIntMersenne::new(Into::<u64>::into(*s));Some(*acc)})).collect();Self{len:s.len(),base_pow_table,prefix_hash_table,}}pub fn len(&self)->usize{self.len}pub fn is_empty(&self)->bool{self.len==0}pub fn get_hash<R:RangeBounds<usize>>(&self,range:R)->ModIntMersenne{let l=match range.start_bound(){std::ops::Bound::Included(&l)=>l,std::ops::Bound::Excluded(&l)=>l+1,std::ops::Bound::Unbounded=>0,};let r=match range.end_bound(){std::ops::Bound::Included(&r)=>r+1,std::ops::Bound::Excluded(&r)=>r,std::ops::Bound::Unbounded=>self.len,};assert!(l<=r&&r<=self.len);self.prefix_hash_table[r]-self.prefix_hash_table[l]*self.base_pow_table[r-l]}pub fn get_base_pow(&self,i:usize)->ModIntMersenne{assert!(i<=self.len);self.base_pow_table[i]}pub fn get_prefix_hash(&self,i:usize)->ModIntMersenne{assert!(i<=self.len);self.prefix_hash_table[i]}}}
    }

    pub(crate) mod macros {
        pub mod algebra {}
        pub mod dual_segtree {}
        pub mod modint_mersenne {}
        pub mod rolling_hash {}
    }

    pub(crate) mod prelude {pub use crate::__cargo_equip::crates::*;}

    mod preludes {
        pub mod algebra {}
        pub mod dual_segtree {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::algebra;}
        pub mod modint_mersenne {}
        pub mod rolling_hash {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::modint_mersenne;}
    }
}
0