結果

問題 No.2761 Substitute and Search
コンテスト
ユーザー LyricalMaestro
提出日時 2025-03-09 03:49:20
言語 Rust
(1.83.0 + proconio)
結果
WA  
実行時間 -
コード長 4,573 bytes
コンパイル時間 13,361 ms
コンパイル使用メモリ 387,864 KB
実行使用メモリ 172,800 KB
最終ジャッジ日時 2025-03-09 03:50:04
合計ジャッジ時間 29,324 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 4 WA * 9
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: variable does not need to be mutable
  --> src/main.rs:68:27
   |
68 |     fn get_sum(&mut self, mut l: usize, mut r: usize) -> u64 {
   |                           ----^
   |                           |
   |                           help: remove this `mut`
   |
   = note: `#[warn(unused_mut)]` on by default

warning: variable does not need to be mutable
  --> src/main.rs:68:41
   |
68 |     fn get_sum(&mut self, mut l: usize, mut r: usize) -> u64 {
   |                                         ----^
   |                                         |
   |                                         help: remove this `mut`

warning: variable `L` should have a snake case name
  --> src/main.rs:70:17
   |
70 |         let mut L = self.size + l;
   |                 ^ help: convert the identifier to snake case: `l`
   |
   = note: `#[warn(non_snake_case)]` on by default

warning: variable `R` should have a snake case name
  --> src/main.rs:71:17
   |
71 |         let mut R = self.size + r;
   |                 ^ help: convert the identifier to snake case: `r`

ソースコード

diff # 

use std::collections::VecDeque;
use std::io::{self, BufRead};

const B: u64 = 30;
const H: u64 = 9007199254740997;

struct SegmentTree {
    size: usize,
    pow_b: Vec<u64>,
    array: Vec<u64>,
    weights: Vec<u64>,
    l_queue: VecDeque<usize>,
    r_queue: VecDeque<usize>,
}

impl SegmentTree {
    fn new(init_array: &[u64], pow_b: &[u64]) -> Self {
        let mut n = 1;
        while n < init_array.len() {
            n *= 2;
        }
        
        let size = n;
        let mut array = vec![0; 2 * size];
        let mut weights = vec![0; 2 * size];
        
        for (i, &a) in init_array.iter().enumerate() {
            array[size + i] = a;
            weights[size + i] = 1;
        }

        let mut start_index = size / 2;
        let mut end_index = size;
        while start_index >= 1 {
            for i in start_index..end_index {
                weights[i] = weights[2 * i] + weights[2 * i + 1];
                array[i] = Self::op(&array, &pow_b, &weights, 2 * i, 2 * i + 1);
            }
            end_index = start_index;
            start_index /= 2;
        }
        
        Self {
            size,
            pow_b: pow_b.to_vec(),
            array,
            weights,
            l_queue: VecDeque::new(),
            r_queue: VecDeque::new(),
        }
    }
    
    fn op(array: &[u64], pow_b: &[u64], weights: &[u64], l: usize, r: usize) -> u64 {
        let mut a = (pow_b[weights[r] as usize] * array[l]) % H;
        a = (a + array[r]) % H;
        a
    }

    fn set(&mut self, x: usize, a: u64) {
        let mut index = self.size + x;
        self.array[index] = a;
        while index > 1 {
            index /= 2;
            self.array[index] = Self::op(&self.array, &self.pow_b, &self.weights, 2 * index, 2 * index + 1);
        }
    }
    
    fn get_sum(&mut self, mut l: usize, mut r: usize) -> u64 {
        let mut s = 0;
        let mut L = self.size + l;
        let mut R = self.size + r;
        
        while L < R {
            if R & 1 == 1 {
                R -= 1;
                self.r_queue.push_front(R);
            }
            if L & 1 == 1 {
                self.l_queue.push_back(L);
                L += 1;
            }
            L /= 2;
            R /= 2;
        }
        
        while let Some(l) = self.l_queue.pop_front() {
            s = (s * self.pow_b[self.weights[l] as usize]) % H;
            s = (s + self.array[l]) % H;
        }
        while let Some(l) = self.r_queue.pop_front() {
            s = (s * self.pow_b[self.weights[l] as usize]) % H;
            s = (s + self.array[l]) % H;
        }
        s
    }
}

fn main() {
    let stdin = io::stdin();
    let mut lines = stdin.lock().lines();
    let first_line = lines.next().unwrap().unwrap();
    let mut iter = first_line.split_whitespace().map(|s| s.parse::<usize>().unwrap());
    let (n, l, q) = (iter.next().unwrap(), iter.next().unwrap(), iter.next().unwrap());
    
    let mut s_arrays = Vec::new();
    let mut segs = Vec::new();
    
    let mut pow_b = vec![0; l + 1];
    let mut b = 1;
    for i in 0..=l {
        pow_b[i] = b;
        b = (b * B) % H;
    }
    
    for _ in 0..n {
        let s = lines.next().unwrap().unwrap();
        let s_array: Vec<u64> = s.chars().map(|c| (c as u64) - ('a' as u64) + 1).collect();
        s_arrays.push(s_array.clone());
        segs.push(SegmentTree::new(&s_array, &pow_b));
    }
    
    for _ in 0..q {
        let query = lines.next().unwrap().unwrap();
        let values: Vec<&str> = query.split_whitespace().collect();
        
        if values[0] == "1" {
            let k = values[1].parse::<usize>().unwrap() - 1;
            let c = (values[2].chars().next().unwrap() as u64) - ('a' as u64) + 1;
            let d = (values[3].chars().next().unwrap() as u64) - ('a' as u64) + 1;
            for i in 0..n {
                if s_arrays[i][k] == c {
                    s_arrays[i][k] = d;
                    segs[i].set(k, d);
                }
            }
        } else if values[0] == "2" {
            let t = values[1];
            let mut t_hash = 0;
            for t0 in t.chars() {
                t_hash = (t_hash * B) % H;
                t_hash = (t_hash + (t0 as u64 - 'a' as u64 + 1)) % H;
            }
            
            let t_len = t.len();
            let mut answer = 0;
            for i in 0..n {
                let x = segs[i].get_sum(0, t_len);
                if t_hash == x {
                    answer += 1;
                }
            }
            println!("{}", answer);
        }
    }
}
0