// codesnip-guard: CompressedBinaryIndexedTree
#[cfg_attr(any(),rustfmt::skip)]pub use self::compressed_binary_indexed_tree::{CompressedBinaryIndexedTree,CompressedBinaryIndexedTree1d,CompressedBinaryIndexedTree2d,CompressedBinaryIndexedTree3d,CompressedBinaryIndexedTree4d};#[cfg_attr(any(),rustfmt::skip)]mod compressed_binary_indexed_tree{use super::Monoid;use std::{fmt::{self,Debug},marker::PhantomData,ops::{Bound,RangeBounds}};pub struct CompressedBinaryIndexedTree<M,X,Inner>where M:Monoid{compress:Vec<X>,bits:Vec<Inner>,_marker:PhantomData<fn()->M>}impl<M,X,Inner>Debug for CompressedBinaryIndexedTree<M,X,Inner>where M:Monoid,X:Debug,Inner:Debug{fn fmt(&self,f:&mut fmt::Formatter<'_>)->fmt::Result{f.debug_struct("CompressedBinaryIndexedTree").field("compress",&self.compress).field("bits",&self.bits).finish()}}impl<M,X,Inner>Clone for CompressedBinaryIndexedTree<M,X,Inner>where M:Monoid,X:Clone,Inner:Clone{fn clone(&self)->Self{Self{compress:self.compress.clone(),bits:self.bits.clone(),_marker:self._marker}}}impl<M,X,Inner>Default for CompressedBinaryIndexedTree<M,X,Inner>where M:Monoid{fn default()->Self{Self{compress:Default::default(),bits:Default::default(),_marker:Default::default()}}}#[repr(transparent)]pub struct Tag<M>(M::T)where M:Monoid;impl<M>Debug for Tag<M>where M:Monoid<T:Debug>{fn fmt(&self,f:&mut fmt::Formatter<'_>)->fmt::Result{self.0 .fmt(f)}}impl<M>Clone for Tag<M>where M:Monoid{fn clone(&self)->Self{Self(self.0 .clone())}}macro_rules!impl_compressed_binary_indexed_tree{(@tuple($($l:tt)*)($($r:tt)*)$T:ident)=>{($($l)*$T$($r)*,)};(@tuple($($l:tt)*)($($r:tt)*)$T:ident$($Rest:ident)+)=>{($($l)*$T$($r)*,impl_compressed_binary_indexed_tree!(@tuple($($l)*)($($r)*)$($Rest)+))};(@cst$M:ident)=>{Tag<$M>};(@cst$M:ident$T:ident$($Rest:ident)*)=>{CompressedBinaryIndexedTree<$M,$T,impl_compressed_binary_indexed_tree!(@cst$M$($Rest)*)>};(@from_iter$M:ident$points:ident$T:ident)=>{{let mut compress:Vec<_> =$points.into_iter().map(|t|t.0 .clone()).collect();compress.sort_unstable();compress.dedup();let n=compress.len();Self{compress,bits:vec![Tag(M::unit());n+1],_marker:PhantomData,}}};(@from_iter$M:ident$points:ident$T:ident$U:ident$($Rest:ident)*)=>{{let mut points:Vec<_> =$points.into_iter().collect();points.sort_unstable_by(|left,right|left.0 .cmp(&right.0));let mut compress=Vec::new();let mut offsets=vec![0];let mut start=0;while start<points.len(){let mut end=start+1;while end<points.len()&&points[end].0==points[start].0{end+=1;}compress.push(points[start].0 .clone());offsets.push(end);start=end;}let n=compress.len();let mut bits:Vec<impl_compressed_binary_indexed_tree!(@cst$M$U$($Rest)*)> =vec![Default::default();n+1];for i in 1..=n{let start=i-(i&(!i+1));bits[i]=<impl_compressed_binary_indexed_tree!(@cst$M$U$($Rest)*)>::from_iter(points[offsets[start]..offsets[i]].iter().map(|point|&point.1),);}Self{compress,bits,_marker:PhantomData,}}};(@acc$e:expr,$rng:ident$T:ident)=>{$e.0};(@acc$e:expr,$rng:ident$T:ident$($Rest:ident)+)=>{$e.accumulate(&$rng.1)};(@update$e:expr,$M:ident$key:ident$x:ident$T:ident)=>{$M::operate_assign(&mut$e.0,$x);};(@update$e:expr,$M:ident$key:ident$x:ident$T:ident$($Rest:ident)+)=>{$e.update(&$key.1,$x);};(@partition_method$T:ident,$Q:ident)=>{pub fn partition_point_acc<P>(&self,mut pred:P)->(Option<&$T>,M::T)where P:FnMut(&M::T)->bool,{let n=self.compress.len();let mut acc=M::unit();let mut pos=0;let mut k=n.next_power_of_two();if k>n{k>>=1;}while k>0{if k+pos<=n{let nacc=M::operate(&acc,&self.bits[k+pos].0);if pred(&nacc){pos+=k;acc=nacc;}}k>>=1;}(self.compress.get(pos),acc)}};(@partition_method$T:ident$($RestT:ident)+,$Q:ident$($RestQ:ident)+)=>{pub fn partition_point_acc<P,$($RestQ,)*>(&self,inner_ranges:&impl_compressed_binary_indexed_tree!(@tuple()()$($RestQ)*),mut pred:P,)->(Option<&$T>,M::T)where P:FnMut(&M::T)->bool,$($RestQ:RangeBounds<$RestT>,)*{let n=self.compress.len();let mut acc=M::unit();let mut pos=0;let mut k=n.next_power_of_two();if k>n{k>>=1;}while k>0{if k+pos<=n{let nacc=M::operate(&acc,&self.bits[k+pos].accumulate(inner_ranges),);if pred(&nacc){pos+=k;acc=nacc;}}k>>=1;}(self.compress.get(pos),acc)}};(@impl$C:ident$($T:ident)*,$($Q:ident)*)=>{impl<M,$($T,)*>impl_compressed_binary_indexed_tree!(@cst M$($T)*)where M:Monoid,$($T:Clone+Ord,)*{pub fn new(points:&[impl_compressed_binary_indexed_tree!(@tuple()()$($T)*)])->Self{Self::from_iter(points)}fn from_iter<'a,Iter>(points:Iter)->Self where$($T:'a,)*Iter:IntoIterator<Item=&'a impl_compressed_binary_indexed_tree!(@tuple()()$($T)*)>+Clone,{impl_compressed_binary_indexed_tree!(@from_iter M points$($T)*)}pub fn accumulate<$($Q,)*>(&self,range:&impl_compressed_binary_indexed_tree!(@tuple()()$($Q)*))->M::T where$($Q:RangeBounds<$T>,)*{match range.0 .start_bound(){Bound::Unbounded=>(),_=>panic!("expected `Bound::Unbounded`"),};let mut k=match range.0 .end_bound(){Bound::Included(index)=>self.compress.partition_point(|x|x<=index),Bound::Excluded(index)=>self.compress.partition_point(|x|x<index),Bound::Unbounded=>self.compress.len(),};let mut x=M::unit();while k>0{x=M::operate(&impl_compressed_binary_indexed_tree!(@acc self.bits[k],range$($T)*),&x);k-=k&(!k+1);}x}pub fn update(&mut self,key:&impl_compressed_binary_indexed_tree!(@tuple()()$($T)*),x:&M::T){let mut k=self.compress.binary_search(&key.0).expect("not exist key")+1;while k<self.bits.len(){impl_compressed_binary_indexed_tree!(@update self.bits[k],M key x$($T)*);k+=k&(!k+1);}}impl_compressed_binary_indexed_tree!(@partition_method$($T)*,$($Q)*);}pub type$C<M,$($T),*> =impl_compressed_binary_indexed_tree!(@cst M$($T)*);};(@inner[$C:ident][$($T:ident)*][$($Q:ident)*][])=>{impl_compressed_binary_indexed_tree!(@impl$C$($T)*,$($Q)*);};(@inner[$C:ident][$($T:ident)*][$($Q:ident)*][$D:ident$U:ident$R:ident$($Rest:ident)*])=>{impl_compressed_binary_indexed_tree!(@impl$C$($T)*,$($Q)*);impl_compressed_binary_indexed_tree!(@inner[$D][$($T)*$U][$($Q)*$R][$($Rest)*]);};($C:ident$T:ident$Q:ident$($Rest:ident)*$(;$($t:tt)*)?)=>{impl_compressed_binary_indexed_tree!(@inner[$C][$T][$Q][$($Rest)*]);};($($t:tt)*)=>{compile_error!($($t:tt)*)}}impl_compressed_binary_indexed_tree!(CompressedBinaryIndexedTree1d A QA CompressedBinaryIndexedTree2d B QB CompressedBinaryIndexedTree3d C QC CompressedBinaryIndexedTree4d D QD;CompressedBinaryIndexedTree5d E QE CompressedBinaryIndexedTree6d F QF CompressedBinaryIndexedTree7d G QG CompressedBinaryIndexedTree8d H QH CompressedBinaryIndexedTree9d I QI);}
// codesnip-guard: algebra
#[cfg_attr(any(),rustfmt::skip)]pub use self::magma::*;#[cfg_attr(any(),rustfmt::skip)]mod magma{#![doc=" algebraic traits"]#[doc=" binary operaion: $T \\circ T \\to T$"]pub trait Magma{#[doc=" type of operands: $T$"]type T:Clone;#[doc=" binary operaion: $\\circ$"]fn operate(x:&Self::T,y:&Self::T)->Self::T;fn reverse_operate(x:&Self::T,y:&Self::T)->Self::T{Self::operate(y,x)}fn operate_assign(x:&mut Self::T,y:&Self::T){*x=Self::operate(x,y);}}#[doc=" $\\forall a,\\forall b,\\forall c \\in T, (a \\circ b) \\circ c = a \\circ (b \\circ c)$"]pub trait Associative:Magma{}#[doc=" associative binary operation"]pub trait SemiGroup:Magma+Associative{}impl<S>SemiGroup for S where S:Magma+Associative{}#[doc=" $\\exists e \\in T, \\forall a \\in T, e \\circ a = a \\circ e = a$"]pub trait Unital:Magma{#[doc=" identity element: $e$"]fn unit()->Self::T;fn is_unit(x:&Self::T)->bool where Self::T:PartialEq{x==&Self::unit()}fn set_unit(x:&mut Self::T){*x=Self::unit();}}pub trait ExpBits{type Iter:Iterator<Item=bool>;fn bits(self)->Self::Iter;}pub trait SignedExpBits{type T:ExpBits;fn neg_and_bits(self)->(bool,Self::T);}pub struct Bits<T>{n:T}macro_rules!impl_exp_bits_for_uint{($($t:ty)*)=>{$(impl Iterator for Bits<$t>{type Item=bool;fn next(&mut self)->Option<bool>{if self.n==0{None}else{let bit=(self.n&1)==1;self.n>>=1;Some(bit)}}}impl ExpBits for$t{type Iter=Bits<$t>;fn bits(self)->Self::Iter{Bits{n:self}}}impl SignedExpBits for$t{type T=$t;fn neg_and_bits(self)->(bool,Self::T){(false,self)}})*};}impl_exp_bits_for_uint!(u8 u16 u32 u64 u128 usize);macro_rules!impl_signed_exp_bits_for_sint{($($s:ty,$u:ty;)*)=>{$(impl SignedExpBits for$s{type T=$u;fn neg_and_bits(self)->(bool,Self::T){(self<0,self.unsigned_abs())}})*};}impl_signed_exp_bits_for_sint!(i8,u8;i16,u16;i32,u32;i64,u64;i128,u128;isize,usize;);#[doc=" associative binary operation and an identity element"]pub trait Monoid:SemiGroup+Unital{#[doc=" binary exponentiation: $x^n = x\\circ\\ddots\\circ x$"]fn pow<E>(mut x:Self::T,exp:E)->Self::T where E:ExpBits{let mut bits=exp.bits();let Some(first)=bits.next()else{return Self::unit();};let mut res=if first{x.clone()}else{Self::unit()};for bit in bits{x=Self::operate(&x,&x);if bit{res=Self::operate(&res,&x);}}res}fn fold<I>(iter:I)->Self::T where I:IntoIterator<Item=Self::T>{let mut iter=iter.into_iter();if let Some(item)=iter.next(){iter.fold(item,|acc,x|Self::operate(&acc,&x))}else{Self::unit()}}}impl<M>Monoid for M where M:SemiGroup+Unital{}#[doc=" $\\exists e \\in T, \\forall a \\in T, \\exists b,c \\in T, b \\circ a = a \\circ c = e$"]pub trait Invertible:Magma+Unital{#[doc=" $a$ where $a \\circ x = e$"]fn inverse(x:&Self::T)->Self::T;fn rinv_operate(x:&Self::T,y:&Self::T)->Self::T{Self::operate(x,&Self::inverse(y))}fn rinv_operate_assign(x:&mut Self::T,y:&Self::T){*x=Self::rinv_operate(x,y);}}#[doc=" associative binary operation and an identity element and inverse elements"]pub trait Group:Monoid+Invertible{fn signed_pow<E>(x:Self::T,exp:E)->Self::T where E:SignedExpBits{let(neg,exp)=E::neg_and_bits(exp);let res=Self::pow(x,exp);if neg{Self::inverse(&res)}else{res}}}impl<G>Group for G where G:Monoid+Invertible{}#[doc=" $\\forall a,\\forall b \\in T, a \\circ b = b \\circ a$"]pub trait Commutative:Magma{}#[doc=" commutative monoid"]pub trait AbelianMonoid:Monoid+Commutative{}impl<M>AbelianMonoid for M where M:Monoid+Commutative{}#[doc=" commutative group"]pub trait AbelianGroup:Group+Commutative{}impl<G>AbelianGroup for G where G:Group+Commutative{}#[doc=" $\\forall a \\in T, a \\circ a = a$"]pub trait Idempotent:Magma{}#[doc=" idempotent monoid"]pub trait IdempotentMonoid:Monoid+Idempotent{}impl<M>IdempotentMonoid for M where M:Monoid+Idempotent{}#[macro_export]macro_rules!monoid_fold{($m:ty)=>{<$m as Unital>::unit()};($m:ty,)=>{<$m as Unital>::unit()};($m:ty,$f:expr)=>{$f};($m:ty,$f:expr,$($ff:expr),*)=>{<$m as Magma>::operate(&($f),&monoid_fold!($m,$($ff),*))};}#[macro_export]macro_rules!define_monoid{($Name:ident,$t:ty,|$x:ident,$y:ident|$op:expr,$unit:expr)=>{struct$Name;impl Magma for$Name{type T=$t;fn operate($x:&Self::T,$y:&Self::T)->Self::T{$op}}impl Unital for$Name{fn unit()->Self::T{$unit}}impl Associative for$Name{}};}}