#982619 (Rust) No.2761 Substitute and Search

提出ソース
結果

問題	No.2761 Substitute and Search
ユーザー	atcoder8
提出日時	2024-05-18 06:48:20
言語	Rust (1.77.0 + proconio)
結果	AC
実行時間	3,666 ms / 4,000 ms
コード長	21,538 bytes
コンパイル時間	12,714 ms
コンパイル使用メモリ	405,204 KB
実行使用メモリ	352,272 KB
最終ジャッジ日時	2024-05-18 06:48:56
合計ジャッジ時間	24,114 ms
ジャッジサーバーID （参考情報）	judge5 / judge1
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,816 KB
testcase_01	AC	1 ms 6,812 KB
testcase_02	AC	1 ms 6,940 KB
testcase_03	AC	1 ms 6,944 KB
testcase_04	AC	2,003 ms 352,272 KB
testcase_05	AC	3,666 ms 340,992 KB
testcase_06	AC	831 ms 340,864 KB
testcase_07	AC	2,378 ms 346,456 KB
testcase_08	AC	843 ms 340,864 KB
testcase_09	AC	2,383 ms 346,576 KB
testcase_10	AC	852 ms 340,992 KB
testcase_11	AC	2,405 ms 346,620 KB
testcase_12	AC	1,604 ms 343,776 KB
testcase_13	AC	1,563 ms 343,660 KB
testcase_14	AC	1,604 ms 343,608 KB
testcase_15	AC	1,615 ms 343,760 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
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::<Vec<S>>(),
        )
    };

    let mut segment_trees = ss.iter().map(|s| chars_to_segtree(s)).collect::<Vec<_>>();

    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<M>
    where
        M: Monoid,
    {
        /// Length of sequence
        n: usize,

        /// Sequences and intermediate data
        data: Vec<M>,
    }

    impl<M: Monoid> From<Vec<M>> for SegmentTree<M> {
        fn from(seq: Vec<M>) -> Self {
            let mut segtree = Self::new(seq.len());
            for (i, x) in seq.into_iter().enumerate() {
                segtree.set(i, x);
            }
            segtree
        }
    }

    impl<M: Monoid> SegmentTree<M> {
        /// 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::<Data>::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<R>(&self, rng: R) -> M
        where
            R: RangeBounds<usize>,
        {
            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<F>(&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<F>(&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 = 2;

    /// 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];

    /// Radixes used to calculate hash values.
    pub const RADIXES: HashValue = [252895580, 406082094];

    /// 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<T, I> From<I> for RollingHash
    where
        HashBlock: From<T>,
        I: IntoIterator<Item = T>,
    {
        /// 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<T>(seq: &[T]) -> Self
        where
            HashBlock: From<T>,
            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<I>(seq: I) -> Self
        where
            I: IntoIterator<Item = usize>,
        {
            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<T>(&mut self, elem: T)
        where
            HashBlock: From<T>,
        {
            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<T, I>(&mut self, elements: I)
        where
            HashBlock: From<T>,
            I: IntoIterator<Item = T>,
        {
            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
        }
    }
}
yukicoder

結果

テストケース

ソースコード
