結果
| 問題 |
No.2761 Substitute and Search
|
| コンテスト | |
| ユーザー |
 atcoder8
|
| 提出日時 | 2024-05-18 06:48:20 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 3,673 ms / 4,000 ms |
| コード長 | 21,538 bytes |
| コンパイル時間 | 14,608 ms |
| コンパイル使用メモリ | 390,892 KB |
| 実行使用メモリ | 352,152 KB |
| 最終ジャッジ日時 | 2024-12-20 16:03:36 |
| 合計ジャッジ時間 | 38,323 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 13 |
ソースコード
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
}
}
}