結果
| 問題 |
No.2761 Substitute and Search
|
| コンテスト | |
| ユーザー |
 CoCo_Japan_pan
|
| 提出日時 | 2024-05-17 23:05:56 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 1,093 ms / 4,000 ms |
| コード長 | 13,307 bytes |
| コンパイル時間 | 17,025 ms |
| コンパイル使用メモリ | 387,360 KB |
| 実行使用メモリ | 115,732 KB |
| 最終ジャッジ日時 | 2024-12-20 15:09:10 |
| 合計ジャッジ時間 | 24,306 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 13 |
ソースコード
#![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;}
}
}