search

tipstar0125 / atcoder

atcoder
6 stars 0 forks source link

ACL移植 #43

Open tipstar0125 opened 8 months ago

tipstar0125 commented 8 months ago

https://github.com/rust-lang-ja/ac-library-rs/tree/master

tipstar0125 commented 8 months ago
Segtree 
fn ceil_pow2(n: u32) -> u32 {
    32 - n.saturating_sub(1).leading_zeros()
}

pub trait Integral:
    'static
    + Send
    + Sync
    + Copy
    + Ord
    + std::ops::Not<Output = Self>
    + std::ops::Add<Output = Self>
    + std::ops::Sub<Output = Self>
    + std::ops::Mul<Output = Self>
    + std::ops::Div<Output = Self>
    + std::ops::Rem<Output = Self>
    + std::ops::AddAssign
    + std::ops::SubAssign
    + std::ops::MulAssign
    + std::ops::DivAssign
    + std::ops::RemAssign
    + std::iter::Sum
    + std::iter::Product
    + std::ops::BitOr<Output = Self>
    + std::ops::BitAnd<Output = Self>
    + std::ops::BitXor<Output = Self>
    + std::ops::BitOrAssign
    + std::ops::BitAndAssign
    + std::ops::BitXorAssign
    + std::ops::Shl<Output = Self>
    + std::ops::Shr<Output = Self>
    + std::ops::ShlAssign
    + std::ops::ShrAssign
    + std::fmt::Display
    + std::fmt::Debug
    + std::fmt::Binary
    + std::fmt::Octal
    + Zero
    + One
    + BoundedBelow
    + BoundedAbove
{
}

/// Class that has additive identity element
pub trait Zero {
    /// The additive identity element
    fn zero() -> Self;
}

/// Class that has multiplicative identity element
pub trait One {
    /// The multiplicative identity element
    fn one() -> Self;
}

pub trait BoundedBelow {
    fn min_value() -> Self;
}

pub trait BoundedAbove {
    fn max_value() -> Self;
}

macro_rules! impl_integral {
    ($($ty:ty),*) => {
        $(
            impl Zero for $ty {
                #[inline]
                fn zero() -> Self {
                    0
                }
            }

            impl One for $ty {
                #[inline]
                fn one() -> Self {
                    1
                }
            }

            impl BoundedBelow for $ty {
                #[inline]
                fn min_value() -> Self {
                    Self::min_value()
                }
            }

            impl BoundedAbove for $ty {
                #[inline]
                fn max_value() -> Self {
                    Self::max_value()
                }
            }

            impl Integral for $ty {}
        )*
    };
}

impl_integral!(i8, i16, i32, i64, i128, isize, u8, u16, u32, u64, u128, usize);

pub trait Monoid {
    type S: Clone;
    fn identity() -> Self::S;
    fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S;
}

pub struct Max<S>(
    std::convert::Infallible,
    std::marker::PhantomData<fn() -> S>,
);
impl<S> Monoid for Max<S>
where
    S: Copy + Ord + BoundedBelow,
{
    type S = S;
    fn identity() -> Self::S {
        S::min_value()
    }
    fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {
        std::cmp::max(*a, *b)
    }
}

pub struct Min<S>(
    std::convert::Infallible,
    std::marker::PhantomData<fn() -> S>,
);
impl<S> Monoid for Min<S>
where
    S: Copy + Ord + BoundedAbove,
{
    type S = S;
    fn identity() -> Self::S {
        S::max_value()
    }
    fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {
        std::cmp::min(*a, *b)
    }
}

pub struct Additive<S>(
    std::convert::Infallible,
    std::marker::PhantomData<fn() -> S>,
);
impl<S> Monoid for Additive<S>
where
    S: Copy + std::ops::Add<Output = S> + Zero,
{
    type S = S;
    fn identity() -> Self::S {
        S::zero()
    }
    fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {
        *a + *b
    }
}

pub struct Multiplicative<S>(
    std::convert::Infallible,
    std::marker::PhantomData<fn() -> S>,
);
impl<S> Monoid for Multiplicative<S>
where
    S: Copy + std::ops::Mul<Output = S> + One,
{
    type S = S;
    fn identity() -> Self::S {
        S::one()
    }
    fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {
        *a * *b
    }
}

pub struct BitwiseOr<S>(
    std::convert::Infallible,
    std::marker::PhantomData<fn() -> S>,
);
impl<S> Monoid for BitwiseOr<S>
where
    S: Copy + std::ops::BitOr<Output = S> + Zero,
{
    type S = S;
    fn identity() -> Self::S {
        S::zero()
    }
    fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {
        *a | *b
    }
}

pub struct BitwiseAnd<S>(
    std::convert::Infallible,
    std::marker::PhantomData<fn() -> S>,
);
impl<S> Monoid for BitwiseAnd<S>
where
    S: Copy + std::ops::BitAnd<Output = S> + std::ops::Not<Output = S> + Zero,
{
    type S = S;
    fn identity() -> Self::S {
        !S::zero()
    }
    fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {
        *a & *b
    }
}

pub struct BitwiseXor<S>(
    std::convert::Infallible,
    std::marker::PhantomData<fn() -> S>,
);
impl<S> Monoid for BitwiseXor<S>
where
    S: Copy + std::ops::BitXor<Output = S> + Zero,
{
    type S = S;
    fn identity() -> Self::S {
        S::zero()
    }
    fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {
        *a ^ *b
    }
}

impl<M: Monoid> Default for Segtree<M> {
    fn default() -> Self {
        Segtree::new(0)
    }
}
impl<M: Monoid> Segtree<M> {
    pub fn new(n: usize) -> Segtree<M> {
        vec![M::identity(); n].into()
    }
}
impl<M: Monoid> From<Vec<M::S>> for Segtree<M> {
    fn from(v: Vec<M::S>) -> Self {
        let n = v.len();
        let log = ceil_pow2(n as u32) as usize;
        let size = 1 << log;
        let mut d = vec![M::identity(); 2 * size];
        d[size..][..n].clone_from_slice(&v);
        let mut ret = Segtree { n, size, log, d };
        for i in (1..size).rev() {
            ret.update(i);
        }
        ret
    }
}
impl<M: Monoid> FromIterator<M::S> for Segtree<M> {
    fn from_iter<T: IntoIterator<Item = M::S>>(iter: T) -> Self {
        let iter = iter.into_iter();
        let n = iter.size_hint().0;
        let log = ceil_pow2(n as u32) as usize;
        let size = 1 << log;
        let mut d = Vec::with_capacity(size * 2);
        d.extend(
            std::iter::repeat_with(M::identity)
                .take(size)
                .chain(iter)
                .chain(std::iter::repeat_with(M::identity).take(size - n)),
        );
        let mut ret = Segtree { n, size, log, d };
        for i in (1..size).rev() {
            ret.update(i);
        }
        ret
    }
}
impl<M: Monoid> Segtree<M> {
    pub fn set(&mut self, mut p: usize, x: M::S) {
        assert!(p < self.n);
        p += self.size;
        self.d[p] = x;
        for i in 1..=self.log {
            self.update(p >> i);
        }
    }

    pub fn get(&self, p: usize) -> M::S {
        assert!(p < self.n);
        self.d[p + self.size].clone()
    }

    pub fn get_slice(&self) -> &[M::S] {
        &self.d[self.size..][..self.n]
    }

    pub fn prod<R>(&self, range: R) -> M::S
    where
        R: std::ops::RangeBounds<usize>,
    {
        // Trivial optimization
        if range.start_bound() == std::ops::Bound::Unbounded
            && range.end_bound() == std::ops::Bound::Unbounded
        {
            return self.all_prod();
        }

        let mut r = match range.end_bound() {
            std::ops::Bound::Included(r) => r + 1,
            std::ops::Bound::Excluded(r) => *r,
            std::ops::Bound::Unbounded => self.n,
        };
        let mut l = match range.start_bound() {
            std::ops::Bound::Included(l) => *l,
            std::ops::Bound::Excluded(l) => l + 1,
            // TODO: There are another way of optimizing [0..r)
            std::ops::Bound::Unbounded => 0,
        };

        assert!(l <= r && r <= self.n);
        let mut sml = M::identity();
        let mut smr = M::identity();
        l += self.size;
        r += self.size;

        while l < r {
            if l & 1 != 0 {
                sml = M::binary_operation(&sml, &self.d[l]);
                l += 1;
            }
            if r & 1 != 0 {
                r -= 1;
                smr = M::binary_operation(&self.d[r], &smr);
            }
            l >>= 1;
            r >>= 1;
        }

        M::binary_operation(&sml, &smr)
    }

    pub fn all_prod(&self) -> M::S {
        self.d[1].clone()
    }

    pub fn max_right<F>(&self, mut l: usize, f: F) -> usize
    where
        F: Fn(&M::S) -> bool,
    {
        assert!(l <= self.n);
        assert!(f(&M::identity()));
        if l == self.n {
            return self.n;
        }
        l += self.size;
        let mut sm = M::identity();
        while {
            // do
            while l % 2 == 0 {
                l >>= 1;
            }
            if !f(&M::binary_operation(&sm, &self.d[l])) {
                while l < self.size {
                    l *= 2;
                    let res = M::binary_operation(&sm, &self.d[l]);
                    if f(&res) {
                        sm = res;
                        l += 1;
                    }
                }
                return l - self.size;
            }
            sm = M::binary_operation(&sm, &self.d[l]);
            l += 1;
            // while
            {
                let l = l as isize;
                (l & -l) != l
            }
        } {}
        self.n
    }

    pub fn min_left<F>(&self, mut r: usize, f: F) -> usize
    where
        F: Fn(&M::S) -> bool,
    {
        assert!(r <= self.n);
        assert!(f(&M::identity()));
        if r == 0 {
            return 0;
        }
        r += self.size;
        let mut sm = M::identity();
        while {
            // do
            r -= 1;
            while r > 1 && r % 2 == 1 {
                r >>= 1;
            }
            if !f(&M::binary_operation(&self.d[r], &sm)) {
                while r < self.size {
                    r = 2 * r + 1;
                    let res = M::binary_operation(&self.d[r], &sm);
                    if f(&res) {
                        sm = res;
                        r -= 1;
                    }
                }
                return r + 1 - self.size;
            }
            sm = M::binary_operation(&self.d[r], &sm);
            // while
            {
                let r = r as isize;
                (r & -r) != r
            }
        } {}
        0
    }

    fn update(&mut self, k: usize) {
        self.d[k] = M::binary_operation(&self.d[2 * k], &self.d[2 * k + 1]);
    }
}

pub struct Segtree<M>
where
    M: Monoid,
{
    // variable name is _n in original library
    n: usize,
    size: usize,
    log: usize,
    d: Vec<M::S>,
}

tipstar0125 commented 8 months ago
Lazy Segtree ```rs fn ceil_pow2(n: u32) -> u32 { 32 - n.saturating_sub(1).leading_zeros() } pub trait Integral: 'static + Send + Sync + Copy + Ord + std::ops::Not + std::ops::Add + std::ops::Sub + std::ops::Mul + std::ops::Div + std::ops::Rem + std::ops::AddAssign + std::ops::SubAssign + std::ops::MulAssign + std::ops::DivAssign + std::ops::RemAssign + std::iter::Sum + std::iter::Product + std::ops::BitOr + std::ops::BitAnd + std::ops::BitXor + std::ops::BitOrAssign + std::ops::BitAndAssign + std::ops::BitXorAssign + std::ops::Shl + std::ops::Shr + std::ops::ShlAssign + std::ops::ShrAssign + std::fmt::Display + std::fmt::Debug + std::fmt::Binary + std::fmt::Octal + Zero + One + BoundedBelow + BoundedAbove { } /// Class that has additive identity element pub trait Zero { /// The additive identity element fn zero() -> Self; } /// Class that has multiplicative identity element pub trait One { /// The multiplicative identity element fn one() -> Self; } pub trait BoundedBelow { fn min_value() -> Self; } pub trait BoundedAbove { fn max_value() -> Self; } macro_rules! impl_integral { ($($ty:ty),*) => { $( impl Zero for $ty { #[inline] fn zero() -> Self { 0 } } impl One for $ty { #[inline] fn one() -> Self { 1 } } impl BoundedBelow for $ty { #[inline] fn min_value() -> Self { Self::min_value() } } impl BoundedAbove for $ty { #[inline] fn max_value() -> Self { Self::max_value() } } impl Integral for $ty {} )* }; } impl_integral!(i8, i16, i32, i64, i128, isize, u8, u16, u32, u64, u128, usize); pub trait Monoid { type S: Clone; fn identity() -> Self::S; fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S; } pub struct Max( std::convert::Infallible, std::marker::PhantomData S>, ); impl Monoid for Max where S: Copy + Ord + BoundedBelow, { type S = S; fn identity() -> Self::S { S::min_value() } fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S { std::cmp::max(*a, *b) } } pub struct Min( std::convert::Infallible, std::marker::PhantomData S>, ); impl Monoid for Min where S: Copy + Ord + BoundedAbove, { type S = S; fn identity() -> Self::S { S::max_value() } fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S { std::cmp::min(*a, *b) } } pub struct Additive( std::convert::Infallible, std::marker::PhantomData S>, ); impl Monoid for Additive where S: Copy + std::ops::Add + Zero, { type S = S; fn identity() -> Self::S { S::zero() } fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S { *a + *b } } pub struct Multiplicative( std::convert::Infallible, std::marker::PhantomData S>, ); impl Monoid for Multiplicative where S: Copy + std::ops::Mul + One, { type S = S; fn identity() -> Self::S { S::one() } fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S { *a * *b } } pub struct BitwiseOr( std::convert::Infallible, std::marker::PhantomData S>, ); impl Monoid for BitwiseOr where S: Copy + std::ops::BitOr + Zero, { type S = S; fn identity() -> Self::S { S::zero() } fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S { *a | *b } } pub struct BitwiseAnd( std::convert::Infallible, std::marker::PhantomData S>, ); impl Monoid for BitwiseAnd where S: Copy + std::ops::BitAnd + std::ops::Not + Zero, { type S = S; fn identity() -> Self::S { !S::zero() } fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S { *a & *b } } pub struct BitwiseXor( std::convert::Infallible, std::marker::PhantomData S>, ); impl Monoid for BitwiseXor where S: Copy + std::ops::BitXor + Zero, { type S = S; fn identity() -> Self::S { S::zero() } fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S { *a ^ *b } } pub trait MapMonoid { type M: Monoid; type F: Clone; // type S = ::S; fn identity_element() -> ::S { Self::M::identity() } fn binary_operation( a: &::S, b: &::S, ) -> ::S { Self::M::binary_operation(a, b) } fn identity_map() -> Self::F; fn mapping(f: &Self::F, x: &::S) -> ::S; fn composition(f: &Self::F, g: &Self::F) -> Self::F; } impl Default for LazySegtree { fn default() -> Self { Self::new(0) } } impl LazySegtree { pub fn new(n: usize) -> Self { vec![F::identity_element(); n].into() } } impl From::S>> for LazySegtree { fn from(v: Vec<::S>) -> Self { let n = v.len(); let log = ceil_pow2(n as u32) as usize; let size = 1 << log; let mut d = vec![F::identity_element(); 2 * size]; let lz = vec![F::identity_map(); size]; d[size..(size + n)].clone_from_slice(&v); let mut ret = LazySegtree { n, size, log, d, lz, }; for i in (1..size).rev() { ret.update(i); } ret } } impl LazySegtree { pub fn set(&mut self, mut p: usize, x: ::S) { assert!(p < self.n); p += self.size; for i in (1..=self.log).rev() { self.push(p >> i); } self.d[p] = x; for i in 1..=self.log { self.update(p >> i); } } pub fn get(&mut self, mut p: usize) -> ::S { assert!(p < self.n); p += self.size; for i in (1..=self.log).rev() { self.push(p >> i); } self.d[p].clone() } pub fn prod(&mut self, range: R) -> ::S where R: RangeBounds, { // Trivial optimization if range.start_bound() == Bound::Unbounded && range.end_bound() == Bound::Unbounded { return self.all_prod(); } let mut r = match range.end_bound() { Bound::Included(r) => r + 1, Bound::Excluded(r) => *r, Bound::Unbounded => self.n, }; let mut l = match range.start_bound() { Bound::Included(l) => *l, Bound::Excluded(l) => l + 1, // TODO: There are another way of optimizing [0..r) Bound::Unbounded => 0, }; assert!(l <= r && r <= self.n); if l == r { return F::identity_element(); } l += self.size; r += self.size; for i in (1..=self.log).rev() { if ((l >> i) << i) != l { self.push(l >> i); } if ((r >> i) << i) != r { self.push(r >> i); } } let mut sml = F::identity_element(); let mut smr = F::identity_element(); while l < r { if l & 1 != 0 { sml = F::binary_operation(&sml, &self.d[l]); l += 1; } if r & 1 != 0 { r -= 1; smr = F::binary_operation(&self.d[r], &smr); } l >>= 1; r >>= 1; } F::binary_operation(&sml, &smr) } pub fn all_prod(&self) -> ::S { self.d[1].clone() } pub fn apply(&mut self, mut p: usize, f: F::F) { assert!(p < self.n); p += self.size; for i in (1..=self.log).rev() { self.push(p >> i); } self.d[p] = F::mapping(&f, &self.d[p]); for i in 1..=self.log { self.update(p >> i); } } pub fn apply_range(&mut self, range: R, f: F::F) where R: RangeBounds, { let mut r = match range.end_bound() { Bound::Included(r) => r + 1, Bound::Excluded(r) => *r, Bound::Unbounded => self.n, }; let mut l = match range.start_bound() { Bound::Included(l) => *l, Bound::Excluded(l) => l + 1, // TODO: There are another way of optimizing [0..r) Bound::Unbounded => 0, }; assert!(l <= r && r <= self.n); if l == r { return; } l += self.size; r += self.size; for i in (1..=self.log).rev() { if ((l >> i) << i) != l { self.push(l >> i); } if ((r >> i) << i) != r { self.push((r - 1) >> i); } } { let l2 = l; let r2 = r; while l < r { if l & 1 != 0 { self.all_apply(l, f.clone()); l += 1; } if r & 1 != 0 { r -= 1; self.all_apply(r, f.clone()); } l >>= 1; r >>= 1; } l = l2; r = r2; } for i in 1..=self.log { if ((l >> i) << i) != l { self.update(l >> i); } if ((r >> i) << i) != r { self.update((r - 1) >> i); } } } pub fn max_right(&mut self, mut l: usize, g: G) -> usize where G: Fn(::S) -> bool, { assert!(l <= self.n); assert!(g(F::identity_element())); if l == self.n { return self.n; } l += self.size; for i in (1..=self.log).rev() { self.push(l >> i); } let mut sm = F::identity_element(); while { // do while l % 2 == 0 { l >>= 1; } if !g(F::binary_operation(&sm, &self.d[l])) { while l < self.size { self.push(l); l *= 2; let res = F::binary_operation(&sm, &self.d[l]); if g(res.clone()) { sm = res; l += 1; } } return l - self.size; } sm = F::binary_operation(&sm, &self.d[l]); l += 1; //while { let l = l as isize; (l & -l) != l } } {} self.n } pub fn min_left(&mut self, mut r: usize, g: G) -> usize where G: Fn(::S) -> bool, { assert!(r <= self.n); assert!(g(F::identity_element())); if r == 0 { return 0; } r += self.size; for i in (1..=self.log).rev() { self.push((r - 1) >> i); } let mut sm = F::identity_element(); while { // do r -= 1; while r > 1 && r % 2 != 0 { r >>= 1; } if !g(F::binary_operation(&self.d[r], &sm)) { while r < self.size { self.push(r); r = 2 * r + 1; let res = F::binary_operation(&self.d[r], &sm); if g(res.clone()) { sm = res; r -= 1; } } return r + 1 - self.size; } sm = F::binary_operation(&self.d[r], &sm); // while { let r = r as isize; (r & -r) != r } } {} 0 } } pub struct LazySegtree where F: MapMonoid, { n: usize, size: usize, log: usize, d: Vec<::S>, lz: Vec, } impl LazySegtree where F: MapMonoid, { fn update(&mut self, k: usize) { self.d[k] = F::binary_operation(&self.d[2 * k], &self.d[2 * k + 1]); } fn all_apply(&mut self, k: usize, f: F::F) { self.d[k] = F::mapping(&f, &self.d[k]); if k < self.size { self.lz[k] = F::composition(&f, &self.lz[k]); } } fn push(&mut self, k: usize) { self.all_apply(2 * k, self.lz[k].clone()); self.all_apply(2 * k + 1, self.lz[k].clone()); self.lz[k] = F::identity_map(); } } // TODO is it useful? use std::{ fmt::{Debug, Error, Formatter, Write}, ops::{Bound, RangeBounds}, }; impl Debug for LazySegtree where F: MapMonoid, F::F: Debug, ::S: Debug, { fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error> { for i in 0..self.log { for j in 0..1 << i { f.write_fmt(format_args!( "{:?}[{:?}]\t", self.d[(1 << i) + j], self.lz[(1 << i) + j] ))?; } f.write_char('\n')?; } for i in 0..self.size { f.write_fmt(format_args!("{:?}\t", self.d[self.size + i]))?; } Ok(()) } } ```
  • © Githubissues.
  • Githubissues is a development platform for aggregating issues.