結果

問題 No.2992 Range ABCD String Query
ユーザー akakimidori
提出日時 2024-12-22 19:25:35
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 249 ms / 6,000 ms
コード長 12,117 bytes
コンパイル時間 13,444 ms
コンパイル使用メモリ 395,424 KB
実行使用メモリ 51,952 KB
最終ジャッジ日時 2024-12-22 19:26:04
合計ジャッジ時間 26,682 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 41
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: type alias `Map` is never used
 --> src/main.rs:4:6
  |
4 | type Map<K, V> = BTreeMap<K, V>;
  |      ^^^
  |
  = note: `#[warn(dead_code)]` on by default

warning: type alias `Set` is never used
 --> src/main.rs:5:6
  |
5 | type Set<T> = BTreeSet<T>;
  |      ^^^

warning: type alias `Deque` is never used
 --> src/main.rs:6:6
  |
6 | type Deque<T> = VecDeque<T>;
  |      ^^^^^

ソースコード

diff #
プレゼンテーションモードにする

use std::collections::*;
use std::io::Write;
type Map<K, V> = BTreeMap<K, V>;
type Set<T> = BTreeSet<T>;
type Deque<T> = VecDeque<T>;
fn main() {
    input! {
        n: usize,
        q: usize,
        s: bytes,
        ask: [(u8, usize1, String); q],
    }
    type Mat = Matrix<V, 4, 4>;
    let mut mat = vec![];
    for i in 0..4 {
        let mut m = Mat::one();
        for j in 0..4 {
            if i != j {
                m[j][j] = V(1);
            }
        }
        let mut trans = Mat::zero();
        for i in 0..4 {
            for j in 0..=i {
                trans[j][i] = V::one();
            }
        }
        mat.push(trans * m);
    }
    let mut seg = SegmentTreePURQ::new(n, Mat::one(), |a, b| *a * *b);
    for (i, s) in s.iter().enumerate() {
        seg.update_tmp(i, mat[(*s - b'A') as usize]);
    }
    seg.update_all();
    let out = std::io::stdout();
    let mut out = std::io::BufWriter::new(out.lock());
    for (op, x, c) in ask {
        if op == 1 {
            let c = c.bytes().next().unwrap();
            seg.update(x, mat[(c - b'A') as usize]);
        } else {
            let l = x;
            let r = c.parse::<usize>().unwrap();
            let m = seg.find(l, r);
            let ans = m[0].iter().fold(V::zero(), |s, a| s + *a).0;
            writeln!(out, "{}", ans).ok();
        }
    }
}
use std::ops::*;
#[derive(Clone, Copy)]
struct V(i32);
impl Add for V {
    type Output = Self;
    fn add(self, rhs: Self) -> Self {
        V(self.0.min(rhs.0))
    }
}
impl Mul for V {
    type Output = Self;
    fn mul(self, rhs: Self) -> Self {
        V(self.0 + rhs.0)
    }
}
const INF: i32 = 10i32.pow(9);
impl Zero for V {
    fn zero() -> Self {
        V(INF)
    }
    fn is_zero(&self) -> bool {
        self.0 == INF
    }
}
impl One for V {
    fn one() -> Self {
        V(0)
    }
    fn is_one(&self) -> bool {
        self.0 == 0
    }
}
// ---------- begin input macro ----------
// reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
#[macro_export]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}
#[macro_export]
macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}
#[macro_export]
macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, bytes) => {
        read_value!($iter, String).bytes().collect::<Vec<u8>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}
// ---------- end input macro ----------
// ---------- begin trait ----------
pub trait Zero: Sized + Add<Self, Output = Self> {
    fn zero() -> Self;
    fn is_zero(&self) -> bool;
}
pub trait One: Sized + Mul<Self, Output = Self> {
    fn one() -> Self;
    fn is_one(&self) -> bool;
}
pub trait Group: Zero + Sub<Output = Self> + Neg<Output = Self> {}
pub trait SemiRing: Zero + One {}
pub trait Ring: SemiRing + Group {}
pub trait Field: Ring + Div<Output = Self> {}
impl<T> Group for T where T: Zero + Sub<Output = Self> + Neg<Output = Self> {}
impl<T> SemiRing for T where T: Zero + One {}
impl<T> Ring for T where T: SemiRing + Group {}
impl<T> Field for T where T: Ring + Div<Output = Self> {}
// ---------- end trait ----------
// ---------- begin const matrix ----------
#[derive(Clone, Copy, Debug)]
pub struct Matrix<T, const R: usize, const C: usize>([[T; C]; R]);
impl<T, const R: usize, const C: usize> Matrix<T, R, C> {
    pub fn new(a: [[T; C]; R]) -> Self {
        Self(a)
    }
    pub fn iter(&self) -> impl Iterator<Item = &[T; C]> {
        self.0.iter()
    }
    pub fn iter_mut(&mut self) -> impl Iterator<Item = &mut [T; C]> {
        self.0.iter_mut()
    }
    pub fn swap_row(&mut self, x: usize, y: usize) {
        assert!(x < R && y < R);
        self.0.swap(x, y);
    }
    pub fn swap_col(&mut self, x: usize, y: usize) {
        assert!(x < C && y < C);
        for mat in self.iter_mut() {
            mat.swap(x, y);
        }
    }
}
impl<T, const R: usize, const C: usize> Zero for Matrix<T, R, C>
where
    T: Zero + Copy,
{
    fn zero() -> Self {
        Self::new([[T::zero(); C]; R])
    }
    fn is_zero(&self) -> bool {
        self.iter().flatten().all(|a| a.is_zero())
    }
}
impl<T, const R: usize, const C: usize> Matrix<T, R, C>
where
    T: Add<Output = T> + Copy,
{
    pub fn matadd(&self, rhs: &Self) -> Self {
        let mut res = self.clone();
        for (res, rhs) in res.iter_mut().zip(rhs.iter()) {
            for (res, rhs) in res.iter_mut().zip(rhs.iter()) {
                *res = *res + *rhs;
            }
        }
        res
    }
}
impl<T, const R: usize, const C: usize> Add for Matrix<T, R, C>
where
    T: Add<Output = T> + Copy,
{
    type Output = Self;
    fn add(self, rhs: Self) -> Self::Output {
        self.matadd(&rhs)
    }
}
impl<T, const R: usize, const C: usize> Matrix<T, R, C>
where
    T: Sub<Output = T> + Copy,
{
    pub fn matsub(&self, rhs: &Self) -> Self {
        let mut res = self.clone();
        for (res, rhs) in res.iter_mut().zip(rhs.iter()) {
            for (res, rhs) in res.iter_mut().zip(rhs.iter()) {
                *res = *res - *rhs;
            }
        }
        res
    }
}
impl<T, const R: usize, const C: usize> Sub for Matrix<T, R, C>
where
    T: Sub<Output = T> + Copy,
{
    type Output = Self;
    fn sub(self, rhs: Self) -> Self::Output {
        self.matsub(&rhs)
    }
}
impl<T, const N: usize> One for Matrix<T, N, N>
where
    T: Zero + One + Copy,
{
    fn one() -> Self {
        let mut res = Self::zero();
        for (i, a) in res.iter_mut().enumerate() {
            a[i] = T::one();
        }
        res
    }
    fn is_one(&self) -> bool {
        self.iter().enumerate().all(|(i, a)| {
            a.iter()
                .enumerate()
                .all(|(j, a)| (i == j && a.is_one()) || (i != j && a.is_zero()))
        })
    }
}
impl<T, const R: usize, const C: usize> Matrix<T, R, C>
where
    T: Zero + Mul<Output = T> + Copy,
{
    pub fn matmul<const M: usize>(&self, rhs: &Matrix<T, C, M>) -> Matrix<T, R, M> {
        let mut res = Matrix::<T, R, M>::zero();
        for (res, a) in res.iter_mut().zip(self.iter()) {
            for (a, b) in a.iter().zip(rhs.iter()) {
                for (res, b) in res.iter_mut().zip(b.iter()) {
                    *res = *res + *a * *b;
                }
            }
        }
        res
    }
}
impl<T, const N: usize> Matrix<T, N, N>
where
    T: SemiRing + Copy,
{
    pub fn matpow(&self, mut n: usize) -> Self {
        let mut t = Self::one();
        let mut r = *self;
        while n > 0 {
            if n & 1 == 1 {
                t = t * r;
            }
            r = r * r;
            n >>= 1;
        }
        t
    }
    // I + A + .. + A^(n-1)
    pub fn powsum(&self, n: usize) -> Self {
        if n == 0 {
            return Self::zero();
        }
        if n & 1 == 1 {
            Self::one() + *self * self.powsum(n - 1)
        } else {
            (Self::one() + *self) * (*self * *self).powsum(n / 2)
        }
    }
}
impl<T, const R: usize, const C: usize, const M: usize> Mul<Matrix<T, C, M>> for Matrix<T, R, C>
where
    T: Zero + Mul<Output = T> + Copy,
{
    type Output = Matrix<T, R, M>;
    fn mul(self, rhs: Matrix<T, C, M>) -> Self::Output {
        self.matmul(&rhs)
    }
}
impl<T, const R: usize, const C: usize> Index<usize> for Matrix<T, R, C> {
    type Output = [T; C];
    fn index(&self, x: usize) -> &Self::Output {
        &self.0[x]
    }
}
impl<T, const R: usize, const C: usize> IndexMut<usize> for Matrix<T, R, C> {
    fn index_mut(&mut self, x: usize) -> &mut Self::Output {
        &mut self.0[x]
    }
}
// ---------- end const matrix ----------
// ---------- begin segment tree Point Update Range Query ----------
pub struct SegmentTreePURQ<T, F> {
    n: usize,
    size: usize,
    data: Vec<T>,
    e: T,
    op: F,
}
impl<T, F> SegmentTreePURQ<T, F>
where
    T: Clone,
    F: Fn(&T, &T) -> T,
{
    pub fn new(n: usize, e: T, op: F) -> Self {
        assert!(n > 0);
        let size = n.next_power_of_two();
        let data = vec![e.clone(); 2 * size];
        SegmentTreePURQ {
            n,
            size,
            data,
            e,
            op,
        }
    }
    pub fn update_tmp(&mut self, x: usize, v: T) {
        assert!(x < self.n);
        self.data[x + self.size] = v;
    }
    pub fn update_all(&mut self) {
        for i in (1..self.size).rev() {
            self.data[i] = (self.op)(&self.data[2 * i], &self.data[2 * i + 1]);
        }
    }
    pub fn update(&mut self, x: usize, v: T) {
        assert!(x < self.n);
        let mut x = x + self.size;
        self.data[x] = v;
        x >>= 1;
        while x > 0 {
            self.data[x] = (self.op)(&self.data[2 * x], &self.data[2 * x + 1]);
            x >>= 1;
        }
    }
    pub fn find(&self, l: usize, r: usize) -> T {
        assert!(l <= r && r <= self.n);
        if l == r {
            return self.e.clone();
        }
        let mut l = self.size + l;
        let mut r = self.size + r;
        let mut x = self.e.clone();
        let mut y = self.e.clone();
        while l < r {
            if l & 1 == 1 {
                x = (self.op)(&x, &self.data[l]);
                l += 1;
            }
            if r & 1 == 1 {
                r -= 1;
                y = (self.op)(&self.data[r], &y);
            }
            l >>= 1;
            r >>= 1;
        }
        (self.op)(&x, &y)
    }
    pub fn max_right<P>(&self, l: usize, f: P) -> usize
    where
        P: Fn(&T) -> bool,
    {
        assert!(l <= self.n);
        assert!(f(&self.e));
        if l == self.n {
            return self.n;
        }
        let mut l = l + self.size;
        let mut sum = self.e.clone();
        while {
            l >>= l.trailing_zeros();
            let v = (self.op)(&sum, &self.data[l]);
            if !f(&v) {
                while l < self.size {
                    l <<= 1;
                    let v = (self.op)(&sum, &self.data[l]);
                    if f(&v) {
                        sum = v;
                        l += 1;
                    }
                }
                return l - self.size;
            }
            sum = v;
            l += 1;
            l.count_ones() > 1
        } {}
        self.n
    }
    pub fn min_left<P>(&self, r: usize, f: P) -> usize
    where
        P: Fn(&T) -> bool,
    {
        assert!(r <= self.n);
        assert!(f(&self.e));
        if r == 0 {
            return 0;
        }
        let mut r = r + self.size;
        let mut sum = self.e.clone();
        while {
            r -= 1;
            while r > 1 && r & 1 == 1 {
                r >>= 1;
            }
            let v = (self.op)(&self.data[r], &sum);
            if !f(&v) {
                while r < self.size {
                    r = 2 * r + 1;
                    let v = (self.op)(&self.data[r], &sum);
                    if f(&v) {
                        sum = v;
                        r -= 1;
                    }
                }
                return r + 1 - self.size;
            }
            sum = v;
            (r & (!r + 1)) != r
        } {}
        0
    }
}
// ---------- end segment tree Point Update Range Query ----------
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0