use std::iter::zip; use proconio::{ input, marker::{Chars, Usize1}, }; use rolling_hash::RollingHash; use segment_tree::Monoid; use crate::segment_tree::SegmentTree; fn main() { input! { (n, _l, q): (usize, usize, usize), mut ss: [Chars; n], } let chars_to_segtree = |s: &[char]| { SegmentTree::from( s.iter() .map(|&c| S(RollingHash::from_slice(&[c]))) .collect::>(), ) }; let mut segment_trees = ss.iter().map(|s| chars_to_segtree(s)).collect::>(); for _ in 0..q { input! { qi: usize, } if qi == 1 { input! { (k, c, d): (Usize1, char, char), } for (s, st) in zip(&mut ss, &mut segment_trees) { if s[k] == c { s[k] = d; st.set(k, S(RollingHash::from_slice(&[d]))); } } } else { input! { t: String, } let hash = RollingHash::from_str(&t); let ans = segment_trees .iter() .filter(|st| st.prod(..t.len()).0 == hash) .count(); println!("{}", ans); } } } #[derive(Debug, Clone, Copy)] struct S(RollingHash); impl Monoid for S { fn id() -> Self { Self(RollingHash::new()) } fn product(&self, rhs: &Self) -> Self { S(self.0.chain(&rhs.0)) } } pub mod segment_tree { //! Performs the following operations on a number sequence of length `n` //! consisting of elements of monoid in logarithmic time of `n`. //! * Updates the specified element //! * Calculates the product of elements in the specified range. use std::ops::RangeBounds; /// Defines the method signature of the monoid. pub trait Monoid: Clone { /// The identity element fn id() -> Self; /// The binary operation fn product(&self, rhs: &Self) -> Self; } /// # Examples /// /// ``` /// # use atcoder8_library::segment_tree::{Monoid, SegmentTree}; /// # /// #[derive(Debug, Clone, PartialEq)] /// struct Data(i32); /// /// impl Monoid for Data { /// fn id() -> Self { /// Data(0) /// } /// /// fn prod(&self, rhs: &Self) -> Self { /// Data(self.0.max(rhs.0)) /// } /// } /// /// let seq = vec![Data(3), Data(-1), Data(4), Data(1), Data(-5), Data(9)]; /// let segtree = SegmentTree::from(seq); /// assert_eq!(segtree.prod(1..5), Data(4)); /// ``` #[derive(Debug, Clone, PartialEq, Eq)] pub struct SegmentTree where M: Monoid, { /// Length of sequence n: usize, /// Sequences and intermediate data data: Vec, } impl From> for SegmentTree { fn from(seq: Vec) -> Self { let mut segtree = Self::new(seq.len()); for (i, x) in seq.into_iter().enumerate() { segtree.set(i, x); } segtree } } impl SegmentTree { /// Creates a Segment Tree for a sequence of length `n`. /// All elements of the sequence are initialized with the identity element. /// /// # Arguments /// /// * `n` - Length of sequence /// /// # Examples /// /// ``` /// # use atcoder8_library::segment_tree::{Monoid, SegmentTree}; /// # /// #[derive(Debug, Clone, PartialEq)] /// struct Data(i32); /// /// impl Monoid for Data { /// fn id() -> Self { /// Data(0) /// } /// /// fn prod(&self, rhs: &Self) -> Self { /// Data(self.0.max(rhs.0)) /// } /// } /// /// let segtree = SegmentTree::::new(5); /// assert_eq!(segtree.get(2), Data(0)); /// ``` pub fn new(n: usize) -> Self { let mut data_len = 1; while data_len < n { data_len *= 2; } data_len *= 2; Self { n, data: vec![M::id(); data_len], } } /// Update the `p`-th number in the sequence to `x`. /// /// # Arguments /// /// * `p` - Index of the element to update /// * `x` - Value to assign /// /// # Examples /// /// ``` /// # use atcoder8_library::segment_tree::{Monoid, SegmentTree}; /// # /// #[derive(Debug, Clone, PartialEq)] /// struct Data(i32); /// /// impl Monoid for Data { /// fn id() -> Self { /// Data(0) /// } /// /// fn prod(&self, rhs: &Self) -> Self { /// Data(self.0.max(rhs.0)) /// } /// } /// /// let seq = vec![Data(3), Data(-1), Data(4)]; /// let mut segtree = SegmentTree::from(seq); /// /// assert_eq!(segtree.get(1), Data(-1)); /// /// segtree.set(1, Data(10)); /// assert_eq!(segtree.get(1), Data(10)); /// ``` pub fn set(&mut self, p: usize, x: M) { assert!( p < self.n, "The specified index {} is outside the range of the sequence; the length of the sequence is {}.", p, self.n, ); let mut p = p + self.data.len() / 2; self.data[p] = x; while p != 1 { p >>= 1; self.data[p] = self.data[2 * p].product(&self.data[2 * p + 1]); } } /// Returns the `p`-th element. /// /// # Arguments /// /// * `p` - Index of the element to get /// /// # Examples /// /// ``` /// # use atcoder8_library::segment_tree::{Monoid, SegmentTree}; /// # /// #[derive(Debug, Clone, PartialEq)] /// struct Data(i32); /// /// impl Monoid for Data { /// fn id() -> Self { /// Data(0) /// } /// /// fn prod(&self, rhs: &Self) -> Self { /// Data(self.0.max(rhs.0)) /// } /// } /// /// let seq = vec![Data(3), Data(-1), Data(4)]; /// let segtree = SegmentTree::from(seq); /// assert_eq!(segtree.get(1), Data(-1)); /// ``` pub fn get(&self, p: usize) -> M { assert!( p < self.n, "The specified index {} is outside the range of the sequence; the length of the sequence is {}.", p, self.n, ); self.data[self.data.len() / 2 + p].clone() } /// Calculates the product of elements of the sequence in the specified range. /// /// # Arguments /// /// * `rng` - Range of the product /// /// # Examples /// /// ``` /// # use atcoder8_library::segment_tree::{Monoid, SegmentTree}; /// # /// #[derive(Debug, Clone, PartialEq)] /// struct Data(i32); /// /// impl Monoid for Data { /// fn id() -> Self { /// Data(0) /// } /// /// fn prod(&self, rhs: &Self) -> Self { /// Data(self.0.max(rhs.0)) /// } /// } /// /// let seq = vec![Data(3), Data(-1), Data(4), Data(1), Data(-5), Data(9)]; /// let segtree = SegmentTree::from(seq); /// /// assert_eq!(segtree.prod(..), Data(9)); /// assert_eq!(segtree.prod(2..), Data(9)); /// assert_eq!(segtree.prod(..5), Data(4)); /// assert_eq!(segtree.prod(2..5), Data(4)); /// assert_eq!(segtree.prod(2..2), Data(0)); /// ``` pub fn prod(&self, rng: R) -> M where R: RangeBounds, { let l = match rng.start_bound() { std::ops::Bound::Included(&start_bound) => start_bound, std::ops::Bound::Excluded(&start_bound) => start_bound + 1, std::ops::Bound::Unbounded => 0, }; let r = match rng.end_bound() { std::ops::Bound::Included(&end_bound) => end_bound + 1, std::ops::Bound::Excluded(&end_bound) => end_bound, std::ops::Bound::Unbounded => self.n, }; assert!(l <= r, "The slice index starts at {} but ends at {}", l, r); assert!( r <= self.n, "The specified range {}..{} is outside the range of the sequence; the length of sequence is {}", l, r, self.n, ); let mut sml = M::id(); let mut smr = M::id(); let mut l = l + self.data.len() / 2; let mut r = r + self.data.len() / 2; while l < r { if l & 1 != 0 { sml = sml.product(&self.data[l]); l += 1; } if r & 1 != 0 { r -= 1; smr = self.data[r].product(&smr); } l >>= 1; r >>= 1; } sml.product(&smr) } /// Returns the product of all elements of a sequence. /// /// # Examples /// /// ``` /// # use atcoder8_library::segment_tree::{Monoid, SegmentTree}; /// # /// #[derive(Debug, Clone, PartialEq)] /// struct Data(i32); /// /// impl Monoid for Data { /// fn id() -> Self { /// Data(0) /// } /// /// fn prod(&self, rhs: &Self) -> Self { /// Data(self.0.max(rhs.0)) /// } /// } /// /// let seq = vec![Data(3), Data(-1), Data(4), Data(1), Data(-5)]; /// let segtree = SegmentTree::from(seq); /// assert_eq!(segtree.all_prod(), Data(4)); /// ``` pub fn all_prod(&self) -> M { self.data[1].clone() } /// Performs a binary search on the segment tree. /// /// Returns one `r` satisfying /// `f(op(seq[l], seq[l + 1], ... , seq[r - 1])) == true` and /// `f(op(seq[l], seq[l + 1], ... , seq[r])) == false`. /// /// If no such `r` exists, returns the maximum index of the sequence plus 1; /// if the length of the sequence is `n`, then `n` is returned. /// /// # Arguments /// /// * `l` - Left boundary of the range of the sequence /// * `f` - Mapping from any element of a monoid to a bool value /// /// # Panics /// /// Panic if any of the following: /// * The identity element is mapped to `false` by `f`. /// * The left boundary `l` is outside the range of the sequence. /// /// # Examples /// /// ``` /// # use atcoder8_library::segment_tree::{Monoid, SegmentTree}; /// # /// #[derive(Debug, Clone, PartialEq)] /// struct Data(usize); /// /// impl Monoid for Data { /// fn id() -> Self { /// Data(0) /// } /// /// fn prod(&self, rhs: &Self) -> Self { /// Data(self.0.max(rhs.0)) /// } /// } /// /// let seq = vec![Data(3), Data(1), Data(4), Data(1), Data(5), Data(9)]; /// let segtree = SegmentTree::from(seq); /// /// assert_eq!(segtree.bs_right_boundary(1, |&Data(x)| x < 1), 1); /// assert_eq!(segtree.bs_right_boundary(1, |&Data(x)| x < 5), 4); /// assert_eq!(segtree.bs_right_boundary(1, |&Data(x)| x < 10), 6); /// ``` pub fn bs_right_boundary(&self, l: usize, f: F) -> usize where F: Fn(&M) -> bool, { assert!( f(&M::id()), "The identity element must be mapped to true by `f`." ); assert!( l <= self.n, "Left boundary {} is outside the range of the sequence; the length of sequence is {}.", l, self.n, ); if l == self.n { return self.n; } let size = self.data.len() / 2; let mut l = l + size; let mut sm = M::id(); loop { while l % 2 == 0 { l >>= 1; } if !f(&sm.product(&self.data[l])) { while l < size { l *= 2; let res = sm.product(&self.data[l]); if f(&res) { sm = res; l += 1; } } return l - size; } sm = sm.product(&self.data[l]); l += 1; if l & l.wrapping_neg() == l { break; } } self.n } /// Performs a binary search on the segment tree. /// /// Returns one `l` satisfying /// `f(op(seq[l], seq[l + 1], ... , seq[r - 1])) == true` and /// `f(op(seq[l - 1], seq[l + 1], ... , seq[r - 1])) == false`. /// /// If no such `l` exists, returns `0`. /// /// # Arguments /// /// * `r` - Right boundary of the range of the sequence /// * `f` - Mapping from any element of a monoid to a bool value /// /// # Panics /// /// Panic if any of the following: /// * The identity element is mapped to `false` by `f`. /// * The right boundary `r` is outside the range of the sequence. /// /// # Examples /// /// ``` /// # use atcoder8_library::segment_tree::{Monoid, SegmentTree}; /// # /// #[derive(Debug, Clone, PartialEq)] /// struct Data(usize); /// /// impl Monoid for Data { /// fn id() -> Self { /// Data(0) /// } /// /// fn prod(&self, rhs: &Self) -> Self { /// Data(self.0.max(rhs.0)) /// } /// } /// /// let seq = vec![Data(3), Data(1), Data(4), Data(1), Data(5), Data(9)]; /// let segtree = SegmentTree::from(seq); /// /// assert_eq!(segtree.bs_left_boundary(4, |&Data(x)| x < 1), 4); /// assert_eq!(segtree.bs_left_boundary(4, |&Data(x)| x < 3), 3); /// assert_eq!(segtree.bs_left_boundary(4, |&Data(x)| x < 5), 0); /// ``` pub fn bs_left_boundary(&self, r: usize, f: F) -> usize where F: Fn(&M) -> bool, { assert!( f(&M::id()), "The identity element must be mapped to true by `f`." ); assert!( r <= self.n, "Right boundary {} is outside the range of the sequence; the length of sequence is {}.", r, self.n, ); if r == 0 { return 0; } let size = self.data.len() / 2; let mut r = r + size; let mut sm = M::id(); loop { r -= 1; while r > 1 && r % 2 == 1 { r >>= 1; } if !f(&self.data[r].product(&sm)) { while r < size { r = 2 * r + 1; let res = self.data[r].product(&sm); if f(&res) { sm = res; r -= 1; } } return r + 1 - size; } sm = self.data[r].product(&sm); if r & r.wrapping_neg() == r { break; } } 0 } } } pub mod rolling_hash { //! Module for rolling hash. /// The type of the blocks that make up the hash. pub type HashBlock = u64; /// Number of integers that make up the hash value. pub const HASH_BLOCK_NUM: usize = 5; /// Type of hash value. /// /// A hash value consists of several integers. pub type HashValue = [HashBlock; HASH_BLOCK_NUM]; /// Moduli used to calculate hash values. pub const MODULI: HashValue = [1000002637, 1000011659, 1000012631, 1000017841, 1000018603]; /// Radixes used to calculate hash values. pub const RADIXES: HashValue = [252895580, 406082094, 892791812, 869052263, 261298120]; /// Generates a hash value from a sequence using Rabin-Karp algorithm. #[derive(Debug, Clone, Copy, PartialEq, Eq)] pub struct RollingHash { /// Length of the sequence. len: usize, /// Hash value corresponding to the sequence. hash_value: HashValue, /// Sequence length power of the radix. /// This array is used to calculate the hash value corresponding to the concatenated sequence. raised_radixes: HashValue, } impl Default for RollingHash { fn default() -> Self { Self { len: 0, hash_value: [0; HASH_BLOCK_NUM], raised_radixes: [1; HASH_BLOCK_NUM], } } } impl From for RollingHash where HashBlock: From, I: IntoIterator, { /// Generates a hash value from a sequence. fn from(seq: I) -> Self { let mut hash = RollingHash::new(); hash.extend(seq); hash } } impl RollingHash { /// Generates a hash value corresponding to an empty sequence. pub fn new() -> Self { Self { len: 0, raised_radixes: [1; HASH_BLOCK_NUM], hash_value: [0; HASH_BLOCK_NUM], } } /// Generates a hash value from a slice of the sequence. pub fn from_slice(seq: &[T]) -> Self where HashBlock: From, T: Copy, { Self::from(seq.iter().cloned()) } /// Generates a hash value from a string slice. #[allow(clippy::should_implement_trait)] pub fn from_str(s: &str) -> Self { Self::from(s.chars()) } /// Generates a hash value from a slice with elements of type `usize`. pub fn from_usize_slice(seq: &[usize]) -> Self { Self::from(seq.iter().map(|&elem| elem as HashBlock)) } /// Generates a hash value from a sequence with elements of type `usize`. pub fn from_usize(seq: I) -> Self where I: IntoIterator, { Self::from(seq.into_iter().map(|elem| elem as HashBlock)) } /// Returns the length of the sequence. pub fn len(&self) -> usize { self.len } /// Returns whether the sequence is empty or not. pub fn is_empty(&self) -> bool { self.len == 0 } /// Adds an element to the end of the sequence. pub fn push(&mut self, elem: T) where HashBlock: From, { self.len += 1; let elem = HashBlock::from(elem); for block_idx in 0..HASH_BLOCK_NUM { let radix = RADIXES[block_idx]; let modulus = MODULI[block_idx]; let block = &mut self.hash_value[block_idx]; *block = (*block * radix % modulus + elem % modulus) % modulus; let raised_radix = &mut self.raised_radixes[block_idx]; *raised_radix = *raised_radix * radix % modulus; } } /// Adds some elements to the end of the sequence. pub fn extend(&mut self, elements: I) where HashBlock: From, I: IntoIterator, { elements.into_iter().for_each(|elem| self.push(elem)); } /// Concatenates another sequence behind the sequence. pub fn concat(&mut self, other: &RollingHash) { self.len += other.len; for (block_idx, modulus) in MODULI.iter().enumerate() { let block = &mut self.hash_value[block_idx]; *block = (*block * other.raised_radixes[block_idx] % modulus + other.hash_value[block_idx]) % modulus; let raised_radix = &mut self.raised_radixes[block_idx]; *raised_radix = *raised_radix * other.raised_radixes[block_idx] % modulus; } } /// Generates a hash value from a chained sequence. pub fn chain(&self, other: &RollingHash) -> Self { let mut concatenated_hash = *self; concatenated_hash.concat(other); concatenated_hash } } }