#1110028 (Rust) No.3208 Parse AND OR Affection

提出ソース
結果

問題	No.3208 Parse AND OR Affection
コンテスト
ユーザー	akakimidori
提出日時	2025-08-02 14:59:33
言語	Rust (1.83.0 + proconio)
結果	AC
実行時間	546 ms / 5,000 ms
コード長	12,712 bytes
コンパイル時間	15,977 ms
コンパイル使用メモリ	396,932 KB
実行使用メモリ	206,084 KB
最終ジャッジ日時	2025-08-02 14:59:58
合計ジャッジ時間	22,745 ms
ジャッジサーバーID （参考情報）	judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 1
other	AC * 20
権限があれば一括ダウンロードができます
ソースコード

raw source code
use std::io::Write;

fn run() {
    input! {
        n: usize,
        q: usize,
        x: bytes,
        ask: [(usize1, usize); q],
    }
    let mut seg = SegmentTreePURQ::new(n, Value::e(), |a, b| a.merge(b));
    for (i, c) in x.iter().enumerate() {
        if i % 2 == 0 {
            seg.update_tmp(i, Value::val(*c));
        } else {
            seg.update_tmp(i, Value::op(*c));
        }
    }
    seg.update_all();
    let out = std::io::stdout();
    let mut out = std::io::BufWriter::new(out.lock());
    for (l, r) in ask {
        writeln!(out, "{}", seg.find(l, r).s[0][0]).ok();
    }
}

const N: usize = 6;

// 0: F
// 1: T
// 2: FF
// 3: TF
// 4: FT
// 5: TT
#[derive(Clone)]
struct Value {
    prod: Matrix<u64, N, N>,
    l: Matrix<u64, 1, N>,
    r: Matrix<u64, N, 1>,
    s: Matrix<u64, 1, 1>,
}

impl Value {
    fn e() -> Self {
        Value {
            prod: one(),
            l: zero(),
            r: zero(),
            s: zero(),
        }
    }
    fn merge(&self, rhs: &Self) -> Self {
        Self {
            prod: self.prod * rhs.prod,
            l: rhs.l + self.l * rhs.prod,
            r: self.r + self.prod * rhs.r,
            s: self.s + rhs.s + self.l * rhs.r,
        }
    }
    fn val(c: u8) -> Self {
        let mut res = Self::e();
        res.prod = zero();
        let c = if c == b'F' {0} else {1};
        for i in 0..4 {
            res.prod[i + 2][i >> c & 1] = 1;
            if i >> c & 1 == 1 {
                res.r[i + 2][0] = 1;
            }
        }
        res.l[0][c] = 1;
        if c == 1 {
            res.s[0][0] = 1;
        }
        res
    }
    fn op(c: u8) -> Self {
        let mut res = Self::e();
        res.prod = zero();
        if c == b'+' {
            res.prod[0][2 + 0b10] = 1;
            res.prod[1][2 + 0b11] = 1;
        } else if c == b'*' {
            res.prod[0][2 + 0b00] = 1;
            res.prod[1][2 + 0b10] = 1;
        } else {
            res.prod[0][2 + 0b10] = 1;
            res.prod[1][2 + 0b01] = 1;
        }
        res
    }
}

fn main() {
    run();
}

// ---------- 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 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 ----------
// ---------- begin trait ----------

use std::ops::*;

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> {}

pub fn zero<T: Zero>() -> T {
    T::zero()
}

pub fn one<T: One>() -> T {
    T::one()
}

pub fn pow<T: One + Clone>(mut r: T, mut n: usize) -> T {
    let mut t = one();
    while n > 0 {
        if n & 1 == 1 {
            t = t * r.clone();
        }
        r = r.clone() * r;
        n >>= 1;
    }
    t
}

pub fn pow_sum<T: SemiRing + Clone>(r: T, n: usize) -> T {
    if n == 0 {
        T::zero()
    } else if n & 1 == 1 {
        T::one() + r.clone() * pow_sum(r, n - 1)
    } else {
        let a = T::one() + r.clone();
        let b = r.clone() * r;
        a * pow_sum(b, n / 2)
    }
}
// ---------- end trait ----------

impl Zero for u64 {
    fn zero() -> Self {
        0
    }
    fn is_zero(&self) -> bool {
        *self == 0
    }
}

impl One for u64 {
    fn one() -> Self {
        1
    }
    fn is_one(&self) -> bool {
        *self == 1
    }
}
// ---------- 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 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> Matrix<T, R, C>
where
    T: Mul<Output = T> + Copy,
{
    pub fn scalar(&self, k: T) -> Self {
        let mut res = *self;
        for a in res.iter_mut().flatten() {
            *a = *a * k;
        }
        res
    }
}

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 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> AddAssign for Matrix<T, R, C>
where
    T: Add<Output = T> + Copy,
{
    fn add_assign(&mut self, rhs: Self) {
        for (a, b) in self.iter_mut().zip(rhs.iter()) {
            for (a, b) in a.iter_mut().zip(b.iter()) {
                *a = *a + *b;
            }
        }
    }
}

impl<T, const R: usize, const C: usize> SubAssign for Matrix<T, R, C>
where
    T: Sub<Output = T> + Copy,
{
    fn sub_assign(&mut self, rhs: Self) {
        for (a, b) in self.iter_mut().zip(rhs.iter()) {
            for (a, b) in a.iter_mut().zip(b.iter()) {
                *a = *a - *b;
            }
        }
    }
}

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(mut self, rhs: Self) -> Self::Output {
        self += rhs;
        self
    }
}

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(mut self, rhs: Self) -> Self::Output {
        self -= rhs;
        self
    }
}

impl<T, const ROW: usize, const COL: usize> Matrix<T, ROW, COL>
where
    T: Zero + Mul<Output = T> + Copy,
{
    pub fn matmul<const NCOL: usize>(&self, rhs: &Matrix<T, COL, NCOL>) -> Matrix<T, ROW, NCOL> {
        let mut res = Matrix::<T, ROW, NCOL>::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 ROW: usize, const COL: usize, const MID: usize> Mul<Matrix<T, MID, COL>>
    for Matrix<T, ROW, MID>
where
    T: Zero + Mul<Output = T> + Copy,
{
    type Output = Matrix<T, ROW, COL>;
    fn mul(self, rhs: Matrix<T, MID, COL>) -> Self::Output {
        self.matmul(&rhs)
    }
}

impl<T, const R: usize, const C: usize> MulAssign<Matrix<T, C, C>> for Matrix<T, R, C>
where
    T: Zero + Mul<Output = T> + Copy,
{
    fn mul_assign(&mut self, rhs: Matrix<T, C, C>) {
        *self = self.matmul(&rhs);
    }
}

impl<T, const R: usize, const C: usize> Deref for Matrix<T, R, C> {
    type Target = [[T; C]; R];
    fn deref(&self) -> &Self::Target {
        &self.0
    }
}

impl<T, const R: usize, const C: usize> DerefMut for Matrix<T, R, C> {
    fn deref_mut(&mut self) -> &mut Self::Target {
        &mut self.0
    }
}
// ---------- end const matrix ----------
yukicoder

結果

ソースコード
