結果
| 問題 |
No.3101 Range Eratosthenes Query
|
| ユーザー |
 37kt
|
| 提出日時 | 2025-05-08 14:09:49 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 430 ms / 3,000 ms |
| コード長 | 26,403 bytes |
| コンパイル時間 | 13,217 ms |
| コンパイル使用メモリ | 391,076 KB |
| 実行使用メモリ | 94,680 KB |
| 最終ジャッジ日時 | 2025-05-08 14:10:16 |
| 合計ジャッジ時間 | 25,312 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 24 |
ソースコード
pub use __cargo_equip::prelude::*;
use linear_sieve::LinearSieve;
#[allow(unused_imports)]
use proconio::{
fastout, input,
marker::{Bytes, Chars, Usize1},
};
use wavelet_matrix::WaveletMatrix;
#[fastout]
fn main() {
input! {
q: usize,
lr: [(usize, usize); q],
}
let sieve = LinearSieve::new(1_000_000);
let a = (0..=1_000_000)
.map(|i| match sieve.least_factor(i) {
None => 1_000_001,
Some(p) if p == i => 1_000_001,
Some(p) => i / p,
})
.collect::<Vec<_>>();
let wm = WaveletMatrix::<usize, true>::new(&a);
for (l, r) in lr {
if l == 1 {
println!("1");
} else {
println!("{}", r + 1 - l - wm.count(l..=r, l..=r));
}
}
}
// The following code was expanded by `cargo-equip`.
/// # Bundled libraries
///
/// - `path+file:///comp_rust/cprs/crates/algebra/algebraic_traits#0.1.0` published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::__algebraic_traits_0_1_0`
/// - `path+file:///comp_rust/cprs/crates/algebra/numeric_traits#0.1.0` published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::numeric_traits`
/// - `path+file:///comp_rust/cprs/crates/data_structure/wavelet_matrix#0.1.0` published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::wavelet_matrix`
/// - `path+file:///comp_rust/cprs/crates/misc/as_half_open_range#0.1.0` published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::as_half_open_range`
/// - `path+file:///comp_rust/cprs/crates/misc/coordinate_compression#0.1.0` published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::coordinate_compression`
/// - `path+file:///comp_rust/cprs/crates/number_theory/linear_sieve#0.1.0` published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::linear_sieve`
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
pub(crate) mod crates {
pub mod __algebraic_traits_0_1_0 {pub use crate::__cargo_equip::macros::__algebraic_traits_0_1_0::*;pub mod traits{pub trait Algebraic{type Value:Clone;}pub trait Magma:Algebraic{fn op(x:&Self::Value,y:&Self::Value)->Self::Value;}pub trait Unital:Magma{fn unit()->Self::Value;fn is_unit(x:&Self::Value)->bool where Self::Value:PartialEq,{&Self::unit()==x}}pub trait Invertive:Magma{fn inv(x:&Self::Value)->Self::Value;}pub trait Associative:Magma{}pub trait Commutative:Magma{}pub trait Idempotent:Magma{}pub trait Semigroup:Associative{}impl<T:Associative>Semigroup for T{}pub trait Monoid:Associative+Unital{}impl<T:Associative+Unital>Monoid for T{}pub trait CommutativeMonoid:Associative+Unital+Commutative{}impl<T:Associative+Unital+Commutative>CommutativeMonoid for T{}pub trait Group:Associative+Unital+Invertive{}impl<T:Associative+Unital+Invertive>Group for T{}pub trait AbelianGroup:Associative+Unital+Commutative+Invertive{}impl<T:Associative+Unital+Commutative+Invertive>AbelianGroup for T{}pub trait Band:Associative+Idempotent{}impl<T:Associative+Idempotent>Band for T{}pub trait Pow:Monoid{fn pow(x:&Self::Value,mut exp:usize)->Self::Value{let mut res=Self::unit();let mut x=Self::op(&res,x);while exp>0{if exp&1==1{res=Self::op(&res,&x);}x=Self::op(&x,&x);exp>>=1;}res}}pub trait Act{type Operand:Monoid;type Operator:Monoid;fn act(x:&<Self::Operand as Algebraic>::Value,f:&<Self::Operator as Algebraic>::Value,)-><Self::Operand as Algebraic>::Value;}pub trait Semiring:Algebraic{type Additive:CommutativeMonoid<Value=Self::Value>;type Multiplicative:Monoid<Value=Self::Value>;fn zero()->Self::Value{Self::Additive::unit()}fn one()->Self::Value{Self::Multiplicative::unit()}fn add(x:&Self::Value,y:&Self::Value)->Self::Value{Self::Additive::op(x,y)}fn mul(x:&Self::Value,y:&Self::Value)->Self::Value{Self::Multiplicative::op(x,y)}}pub trait Ring:Semiring where Self::Additive:Invertive,{fn neg(x:&Self::Value)->Self::Value{Self::Additive::inv(x)}fn sub(x:&Self::Value,y:&Self::Value)->Self::Value{Self::Additive::op(x,&Self::neg(y))}}impl<T>Ring for T where T:Semiring,T::Additive:Invertive,{}pub trait Field:Ring where Self::Additive:Invertive,Self::Multiplicative:Invertive,{fn recip(x:&Self::Value)->Self::Value{Self::Multiplicative::inv(x)}fn div(x:&Self::Value,y:&Self::Value)->Self::Value{Self::Multiplicative::op(x,&Self::recip(y))}}impl<T>Field for T where T:Ring,T::Additive:Invertive,T::Multiplicative:Invertive,{}}pub use traits::*;pub mod macros{#[macro_export]macro_rules!__cargo_equip_macro_def___algebraic_traits_0_1_0_define_algebra{(name:$name:ident,value:$value:ty)=>{enum$name{}impl$crate::__cargo_equip::crates::__algebraic_traits_0_1_0::Algebraic for$name{type Value=$value;}};($vis:vis,name:$name:ident,value:$value:ty)=>{$vis enum$name{}impl$crate::__cargo_equip::crates::__algebraic_traits_0_1_0::Algebraic for$name{type Value=$value;}};(name:$name:ident,value:$value:ty,$($rest:tt)*)=>{define_algebra!(name:$name,value:$value);define_algebra!(@impl$name,$($rest)*);};($vis:vis,name:$name:ident,value:$value:ty,$($rest:tt)*)=>{define_algebra!($vis,name:$name,value:$value);define_algebra!(@impl$name,$($rest)*);};(@impl$name:ident,op:$op:expr,$($rest:tt)*)=>{impl$crate::__cargo_equip::crates::__algebraic_traits_0_1_0::Magma for$name{fn op(x:&Self::Value,y:&Self::Value)->Self::Value{$op(x,y)}}define_algebra!(@impl$name,$($rest)*);};(@impl$name:ident,unit:$unit:expr,$($rest:tt)*)=>{impl$crate::__cargo_equip::crates::__algebraic_traits_0_1_0::Unital for$name{fn unit()->Self::Value{$unit}}define_algebra!(@impl$name,$($rest)*);};(@impl$name:ident,inv:$inv:expr,$($rest:tt)*)=>{impl$crate::__cargo_equip::crates::__algebraic_traits_0_1_0::Invertive for$name{fn inv(x:&Self::Value)->Self::Value{$inv(x)}}define_algebra!(@impl$name,$($rest)*);};(@impl$name:ident,associative,$($rest:tt)*)=>{impl$crate::__cargo_equip::crates::__algebraic_traits_0_1_0::Associative for$name{}define_algebra!(@impl$name,$($rest)*);};(@impl$name:ident,commutative,$($rest:tt)*)=>{impl$crate::__cargo_equip::crates::__algebraic_traits_0_1_0::Commutative for$name{}define_algebra!(@impl$name,$($rest)*);};(@impl$name:ident,idempotent,$($rest:tt)*)=>{impl$crate::__cargo_equip::crates::__algebraic_traits_0_1_0::Idempotent for$name{}define_algebra!(@impl$name,$($rest)*);};(@impl$name:ident$(,)?)=>{};}macro_rules!define_algebra{($($tt:tt)*)=>(crate::__cargo_equip_macro_def___algebraic_traits_0_1_0_define_algebra!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def___algebraic_traits_0_1_0_define_act{(name:$name:ident,operand:$operand:ty,operator:$operator:ty,act:$act:expr$(,)*)=>{enum$name{}impl$crate::__cargo_equip::crates::__algebraic_traits_0_1_0::Act for$name{type Operand=$operand;type Operator=$operator;fn act(x:&<Self::Operand as$crate::__cargo_equip::crates::__algebraic_traits_0_1_0::Algebraic>::Value,f:&<Self::Operator as$crate::__cargo_equip::crates::__algebraic_traits_0_1_0::Algebraic>::Value,)-><Self::Operand as$crate::__cargo_equip::crates::__algebraic_traits_0_1_0::Algebraic>::Value{$act(x,f)}}};($vis:vis,name:$name:ident,operand:$operand:ty,operator:$operator:ty,act:$act:expr$(,)*)=>{$vis enum$name{}impl$crate::__cargo_equip::crates::__algebraic_traits_0_1_0::Act for$name{type Operand=$operand;type Operator=$operator;fn act(x:&<Self::Operand as$crate::__cargo_equip::crates::__algebraic_traits_0_1_0::Algebraic>::Value,f:&<Self::Operator as$crate::__cargo_equip::crates::__algebraic_traits_0_1_0::Algebraic>::Value,)-><Self::Operand as$crate::__cargo_equip::crates::__algebraic_traits_0_1_0::Algebraic>::Value{$act(x,f)}}};}macro_rules!define_act{($($tt:tt)*)=>(crate::__cargo_equip_macro_def___algebraic_traits_0_1_0_define_act!{$($tt)*})}}#[allow(unused_imports)]pub use macros::*;}
pub mod numeric_traits {pub mod inf{pub trait Inf:PartialOrd{fn inf()->Self;}pub trait NegInf:PartialOrd{fn neg_inf()->Self;}macro_rules!impl_inf{($($t:ty,$inf:expr,)*)=>{$(impl Inf for$t{fn inf()->Self{$inf}})*}}macro_rules!impl_neg_inf{($($t:ty,$neg_inf:expr,)*)=>{$(impl NegInf for$t{fn neg_inf()->Self{$neg_inf}})*}}impl_inf!{i32,1_001_000_000,u32,1_001_000_000,f32,1e10,i64,4_004_000_000_000_000_000,isize,4_004_000_000_000_000_000,u64,4_004_000_000_000_000_000,usize,4_004_000_000_000_000_000,f64,1e20,i128,8_008_000_000_000_000_000_000_000_000_000_000_000,u128,8_008_000_000_000_000_000_000_000_000_000_000_000,}impl_neg_inf!{i32,-1_001_000_000,u32,0,f32,-1e10,i64,-4_004_000_000_000_000_000,isize,-4_004_000_000_000_000_000,u64,0,usize,0,f64,-1e20,i128,-8_008_000_000_000_000_000_000_000_000_000_000_000,u128,0,}}pub use inf::*;pub mod zero_one{use std::ops::{Add,Mul};pub trait Zero:Sized+Add<Output=Self>{fn zero()->Self;}pub trait One:Sized+Mul<Output=Self>{fn one()->Self;}macro_rules!impl_zero_one{($($t:ty),*)=>{$(impl Zero for$t{fn zero()->Self{0 as$t}}impl One for$t{fn one()->Self{1 as$t}})*}}impl_zero_one!(u8,u16,u32,u64,u128,usize,i8,i16,i32,i64,i128,isize,f32,f64);}pub use zero_one::*;pub mod cast{pub trait Cast<T>{fn cast(self)->T;}macro_rules!impl_cast_2{($t1:ty,$($t2:ty),*)=>{$(impl Cast<$t2>for$t1{fn cast(self)->$t2{self as$t2}})*}}macro_rules!impl_cast_1{($($t:ty),*)=>{$(impl_cast_2!{$t,u8,u16,u32,u64,u128,i8,i16,i32,i64,i128,usize,isize,f32,f64})*}}impl_cast_1!{u8,u16,u32,u64,u128,i8,i16,i32,i64,i128,usize,isize,f32,f64}}pub use cast::*;pub mod numeric{use std::ops::{Add,AddAssign,Div,DivAssign,Mul,MulAssign,Sub,SubAssign};use crate::__cargo_equip::crates::numeric_traits::zero_one;pub trait Numeric:Sized+Clone+Copy+std::fmt::Debug+std::fmt::Display+PartialEq+Add<Output=Self>+AddAssign+Sub<Output=Self>+SubAssign+Mul<Output=Self>+MulAssign+Div<Output=Self>+DivAssign+zero_one::Zero+zero_one::One{}macro_rules!impl_numeric{($($t:ty),*)=>{$(impl Numeric for$t{})*};}impl_numeric!{u8,u16,u32,u64,u128,i8,i16,i32,i64,i128,usize,isize,f32,f64}}pub use numeric::*;pub mod integer{use std::ops::{BitAnd,BitAndAssign,BitOr,BitOrAssign,BitXor,BitXorAssign,Rem,RemAssign,Shl,ShlAssign,Shr,ShrAssign,};use crate::__cargo_equip::crates::numeric_traits::Numeric;pub trait Integer:Numeric+Eq+Ord+std::hash::Hash+Rem<Output=Self>+RemAssign+BitXor<Output=Self>+BitXorAssign+BitAnd<Output=Self>+BitAndAssign+BitOr<Output=Self>+BitOrAssign+Shl<usize,Output=Self>+ShlAssign<usize>+Shr<usize,Output=Self>+ShrAssign<usize>{const MIN:Self;const MAX:Self;fn popcount(self)->usize;fn msb_index(self)->usize;fn lsb_index(self)->usize;fn msb(self)->Self;fn lsb(self)->Self;fn ceil_pow2(self)->Self;fn floor_pow2(self)->Self;fn ceil_log2(self)->usize;fn floor_log2(self)->usize;fn checked_msb_index(self)->Option<usize>;fn checked_lsb_index(self)->Option<usize>;fn checked_ceil_pow2(self)->Option<Self>;fn checked_floor_pow2(self)->Option<Self>;fn checked_ceil_log2(self)->Option<usize>;fn checked_floor_log2(self)->Option<usize>;fn floor_div(self,other:Self)->Self;fn ceil_div(self,other:Self)->Self;fn gcd(self,other:Self)->Self;fn lcm(self,other:Self)->Self;}macro_rules!impl_integer{($($t:ty),*)=>{$(impl Integer for$t{const MIN:Self=<$t>::MIN;const MAX:Self=<$t>::MAX;fn popcount(self)->usize{self.count_ones()as usize}fn msb_index(self)->usize{(<$t>::BITS-1-self.leading_zeros())as usize}fn lsb_index(self)->usize{self.trailing_zeros()as usize}fn msb(self)->Self{if self==0{0}else{1<<self.msb_index()}}fn lsb(self)->Self{self&self.wrapping_neg()}fn ceil_pow2(self)->Self{1<<self.ceil_log2()}fn floor_pow2(self)->Self{assert!(self>0);self.msb()}fn ceil_log2(self)->usize{assert!(self>0);(<$t>::BITS-(self-1).leading_zeros())as usize}fn floor_log2(self)->usize{assert!(self>0);self.msb_index()}fn checked_msb_index(self)->Option<usize>{if self==0{None}else{Some(self.msb_index())}}fn checked_lsb_index(self)->Option<usize>{if self==0{None}else{Some(self.lsb_index())}}fn checked_ceil_pow2(self)->Option<Self>{if self<=0{None}else{Some(self.ceil_pow2())}}fn checked_floor_pow2(self)->Option<Self>{if self<=0{None}else{Some(self.floor_pow2())}}fn checked_ceil_log2(self)->Option<usize>{if self<=0{None}else{Some(self.ceil_log2())}}fn checked_floor_log2(self)->Option<usize>{if self<=0{None}else{Some(self.floor_log2())}}#[allow(unused_comparisons)]fn floor_div(self,other:Self)->Self{self/other-if self^other<0&&self%other!=0{1}else{0}}#[allow(unused_comparisons)]fn ceil_div(self,other:Self)->Self{self/other+if self^other>=0&&self%other!=0{1}else{0}}#[allow(unused_comparisons)]fn gcd(self,other:Self)->Self{let mut x=if self<0{0-self}else{self};let mut y=if other<0{0-other}else{other};if x==0||y==0{return x|y;}let n=x.trailing_zeros();let m=y.trailing_zeros();x>>=n;y>>=m;while x!=y{if x>y{x-=y;x>>=x.trailing_zeros();}else{y-=x;y>>=y.trailing_zeros();}}x<<n.min(m)}fn lcm(self,other:Self)->Self{self/self.gcd(other)*other}})*};}impl_integer!{u8,u16,u32,u64,u128,i8,i16,i32,i64,i128,usize,isize}}pub use integer::*;pub mod signed{use std::ops::Neg;pub trait Signed:Sized+Neg<Output=Self>{fn signum(self)->Self;}macro_rules!impl_signed_integer{($($t:ty),*)=>{$(impl Signed for$t{fn signum(self)->Self{match self{n if n>0=>1,0=>0,_=>-1,}}})*};}macro_rules!impl_signed_float{($($t:ty),*)=>{$(impl Signed for$t{fn signum(self)->Self{if self.is_nan(){self}else if self==0.0{0.0}else if self>0.0{1.0}else{-1.0}}})*};}impl_signed_integer!{i8,i16,i32,i64,i128,isize}impl_signed_float!{f32,f64}}pub use signed::*;pub trait Recip{fn recip(self)->Self;}impl Recip for f32{fn recip(self)->Self{self.recip()}}impl Recip for f64{fn recip(self)->Self{self.recip()}}}
pub mod wavelet_matrix {use crate::__cargo_equip::preludes::wavelet_matrix::*;use std::{borrow::Borrow,ops::{Range,RangeBounds},};use as_half_open_range::AsHalfOpenRange;use bit_vector::BitVector;use coordinate_compression::CoordinateCompression;use numeric_traits::{Cast,Inf,Integer,NegInf};mod bit_vector{use crate::__cargo_equip::preludes::wavelet_matrix::*;use numeric_traits::Integer;const W:usize=64;#[derive(Clone)]pub(in crate::__cargo_equip::crates::wavelet_matrix)struct BitVector{n:usize,bit:Vec<u64>,sum:Vec<u32>,}impl BitVector{pub(in crate::__cargo_equip::crates::wavelet_matrix)fn new(n:usize)->Self{let sz=(n+1).ceil_div(W);Self{n,bit:vec![0;sz],sum:vec![0;sz+1],}}pub(in crate::__cargo_equip::crates::wavelet_matrix)fn set(&mut self,i:usize){assert!(i<self.n);self.bit[i/W]|=1<<(i%W);}pub(in crate::__cargo_equip::crates::wavelet_matrix)fn build(&mut self){for i in 0..self.bit.len(){self.sum[i+1]=self.sum[i]+self.bit[i].count_ones();}}pub(in crate::__cargo_equip::crates::wavelet_matrix)fn get(&self,i:usize)->bool{(self.bit[i/W]>>(i%W))&1!=0}pub(in crate::__cargo_equip::crates::wavelet_matrix)fn count_prefix(&self,i:usize,f:bool)->usize{let cnt=(self.sum[i/W]+(self.bit[i/W]&((1<<(i%W))-1)).count_ones())as usize;if f{cnt}else{i-cnt}}}}mod internal{use crate::__cargo_equip::preludes::wavelet_matrix::*;use std::ops::Range;use numeric_traits::{Cast,Inf,Integer,NegInf};use crate::__cargo_equip::crates::wavelet_matrix::WaveletMatrix2D;impl<X,Y,const X_SMALL:bool,const Y_SMALL:bool,const INVERTIVE:bool>WaveletMatrix2D<X,Y,X_SMALL,Y_SMALL,INVERTIVE>where X:Integer+Inf+NegInf+Cast<usize>,Y:Integer+Inf+NegInf+Cast<usize>,u32:Cast<X>,u32:Cast<Y>,{pub(in crate::__cargo_equip::crates::wavelet_matrix)fn count_with_(&self,xl:usize,xr:usize,yl:usize,yr:usize,mut f:impl FnMut(usize,Range<usize>,bool),)->usize{if INVERTIVE{self.count_prefix_with_(xl,xr,yr,&mut f)-self.count_prefix_with_(xl,xr,yl,|d,x,inv|f(d,x,!inv))}else{self.dfs_count_with_(self.lg,xl,xr,yl,yr,0,1<<self.lg,&mut f)}}#[allow(clippy::too_many_arguments)]fn dfs_count_with_(&self,d:usize,xl:usize,xr:usize,yl:usize,yr:usize,a:usize,b:usize,f:&mut impl FnMut(usize,Range<usize>,bool),)->usize{if yr<=a||b<=yl{return 0;}else if yl<=a&&b<=yr{f(d,xl..xr,false);return xr-xl;}let d=d-1;let c=(a+b)>>1;let l0=self.bv[d].count_prefix(xl,false);let r0=self.bv[d].count_prefix(xr,false);let l1=xl+self.mid[d]-l0;let r1=xr+self.mid[d]-r0;self.dfs_count_with_(d,l0,r0,yl,yr,a,c,f)+self.dfs_count_with_(d,l1,r1,yl,yr,c,b,f)}fn count_prefix_with_(&self,mut xl:usize,mut xr:usize,y:usize,mut f:impl FnMut(usize,Range<usize>,bool),)->usize{if xl==xr||y==0{return 0;}else if y==self.m{f(self.lg,xl..xr,false);return xr-xl;}let mut cnt=0;for d in(0..self.lg).rev(){let l0=self.bv[d].count_prefix(xl,false);let r0=self.bv[d].count_prefix(xr,false);let l1=xl+self.mid[d]-l0;let r1=xr+self.mid[d]-r0;if y>>d&1==0{(xl,xr)=(l0,r0);}else{f(d,l0..r0,false);cnt+=r0-l0;(xl,xr)=(l1,r1);}}cnt}}}pub type WaveletMatrix<Y,const Y_SMALL:bool=false,const INVERTIVE:bool=false> =WaveletMatrix2D<usize,Y,true,Y_SMALL,INVERTIVE>;impl<Y,const Y_SMALL:bool,const INVERTIVE:bool>WaveletMatrix<Y,Y_SMALL,INVERTIVE>where Y:Integer+Inf+NegInf+Cast<usize>,u32:Cast<Y>,{pub fn new<I>(a:I)->Self where I:IntoIterator,I::Item:Borrow<Y>,{Self::new_with_containers(a,|_|()).0}pub fn new_with_containers<Container,I>(a:I,build_container:impl FnMut(&[usize])->Container,)->(Self,Vec<Container>)where I:IntoIterator,I::Item:Borrow<Y>,{WaveletMatrix2D::<usize,Y,true,Y_SMALL,INVERTIVE>::new_2d_with_containers(a.into_iter().enumerate().map(|(i,y)|(i,*y.borrow())),build_container,)}}pub struct WaveletMatrix2D<X,Y,const X_SMALL:bool=false,const Y_SMALL:bool=false,const INVERTIVE:bool=false,>where X:Integer+Inf+NegInf+Cast<usize>,Y:Integer+Inf+NegInf+Cast<usize>,u32:Cast<X>,u32:Cast<Y>,{n:usize,m:usize,lg:usize,ccx:CoordinateCompression<X,X_SMALL,true>,ccy:CoordinateCompression<Y,Y_SMALL,false>,pos:Vec<usize>,mid:Vec<usize>,bv:Vec<BitVector>,}impl<X,Y,const X_SMALL:bool,const Y_SMALL:bool,const INVERTIVE:bool>WaveletMatrix2D<X,Y,X_SMALL,Y_SMALL,INVERTIVE>where X:Integer+Inf+NegInf+Cast<usize>,Y:Integer+Inf+NegInf+Cast<usize>,u32:Cast<X>,u32:Cast<Y>,{pub fn new_2d<I>(ps:I)->Self where I:IntoIterator,I::Item:Borrow<(X,Y)>,{Self::new_2d_with_containers(ps,|_|()).0}pub fn new_2d_with_containers<Container,I>(ps:I,mut build_container:impl FnMut(&[usize])->Container,)->(Self,Vec<Container>)where I:IntoIterator,I::Item:Borrow<(X,Y)>,{let ps=ps.into_iter().map(|p|*p.borrow()).collect::<Vec<_>>();let n=ps.len();let(ccx,pos)=CoordinateCompression::<X,X_SMALL,true>::new(ps.iter().map(|&(x,_)|x));let(ccy,_)=CoordinateCompression::<Y,Y_SMALL,false>::new(ps.iter().map(|&(_,y)|y));let m=ccy.len();let lg=m.checked_ceil_log2().unwrap_or(0);let mut a=vec![0;n];let mut b=vec![0;n];for i in 0..n{a[pos[i]]=i;b[pos[i]]=ccy.encode(ps[i].1);}let mut mid=vec![0;lg];let mut bv=vec![BitVector::new(n);lg];let mut containers=Vec::with_capacity(lg+1);containers.push(build_container(&a));let mut a0=vec![0;n];let mut a1=vec![0;n];let mut b0=vec![0;n];let mut b1=vec![0;n];for d in(0..lg).rev(){let mut p0=0;let mut p1=0;for i in 0..n{if b[i]>>d&1==0{a0[p0]=a[i];b0[p0]=b[i];p0+=1;}else{bv[d].set(i);a1[p1]=a[i];b1[p1]=b[i];p1+=1;}}a[..p0].copy_from_slice(&a0[..p0]);a[p0..].copy_from_slice(&a1[..p1]);b[..p0].copy_from_slice(&b0[..p0]);b[p0..].copy_from_slice(&b1[..p1]);mid[d]=p0;bv[d].build();containers.push(build_container(&a));}containers.reverse();(Self{n,m,lg,ccx,ccy,pos,mid,bv,},containers,)}pub fn len(&self)->usize{self.n}pub fn is_empty(&self)->bool{self.n==0}pub fn map_index(&self,i:usize)->usize{self.pos[i]}pub fn count(&self,x_range:impl RangeBounds<X>,y_range:impl RangeBounds<Y>)->usize{self.count_with(x_range,y_range,|_,_,_|{})}pub fn count_with(&self,x_range:impl RangeBounds<X>,y_range:impl RangeBounds<Y>,mut f:impl FnMut(usize,Range<usize>,bool),)->usize{let(xl,xr)=x_range.as_half_open_range(X::neg_inf(),X::inf());let(yl,yr)=y_range.as_half_open_range(Y::neg_inf(),Y::inf());let xl=self.ccx.encode(xl);let xr=self.ccx.encode(xr);let yl=self.ccy.encode(yl);let yr=self.ccy.encode(yr);self.count_with_(xl,xr,yl,yr,&mut f)}pub fn access(&self,i:usize)->Y{self.access_with(i,|_,_|{})}pub fn access_with(&self,i:usize,mut f:impl FnMut(usize,usize))->Y{let mut y=0;let mut i=self.map_index(i);f(self.lg,i);for d in(0..self.lg).rev(){if self.bv[d].get(i){y|=1<<d;i=self.bv[d].count_prefix(i,true)+self.mid[d];}else{i=self.bv[d].count_prefix(i,false);}f(d,i);}self.ccy.decode(y)}pub fn kth_smallest(&self,x_range:impl RangeBounds<X>,mut k:usize)->Option<Y>{let(xl,xr)=x_range.as_half_open_range(X::neg_inf(),X::inf());let mut xl=self.ccx.encode(xl);let mut xr=self.ccx.encode(xr);if k>=xr-xl{return None;}let mut y=0;for d in(0..self.lg).rev(){let l0=self.bv[d].count_prefix(xl,false);let r0=self.bv[d].count_prefix(xr,false);let l1=xl+self.mid[d]-l0;let r1=xr+self.mid[d]-r0;if k<r0-l0{(xl,xr)=(l0,r0);}else{k-=r0-l0;y|=1<<d;(xl,xr)=(l1,r1);}}Some(self.ccy.decode(y))}pub fn kth_largest(&self,x_range:impl RangeBounds<X>,k:usize)->Option<Y>{let(xl,xr)=x_range.as_half_open_range(X::neg_inf(),X::inf());let xl=self.ccx.encode(xl);let xr=self.ccx.encode(xr);if k>=xr-xl{return None;}self.kth_smallest(x_range,xr-xl-1-k)}}}
pub mod as_half_open_range {use crate::__cargo_equip::preludes::as_half_open_range::*;use std::ops::{Bound,RangeBounds};use numeric_traits::Integer;pub trait AsHalfOpenRange<T>:RangeBounds<T>where T:Integer,{fn as_half_open_range(&self,l:T,r:T)->(T,T){let start=match self.start_bound(){Bound::Unbounded=>l,Bound::Included(&start)=>start,Bound::Excluded(&start)=>start+T::one(),};let end=match self.end_bound(){Bound::Unbounded=>r,Bound::Included(&end)=>end+T::one(),Bound::Excluded(&end)=>end,};assert!(l<=start&&start<=end&&end<=r);(start,end)}}impl<R,T>AsHalfOpenRange<T>for R where R:RangeBounds<T>,T:Integer,{}}
pub mod coordinate_compression {use crate::__cargo_equip::preludes::coordinate_compression::*;use numeric_traits::{Cast,Integer};#[derive(Clone)]pub struct CoordinateCompression<T,const SMALL:bool=false,const DISTINCT:bool=false>(Container<T>,)where T:Integer+Cast<usize>,u32:Cast<T>;impl<T,const SMALL:bool,const DISTINCT:bool>CoordinateCompression<T,SMALL,DISTINCT>where T:Integer+Cast<usize>,u32:Cast<T>,{pub fn new(xs:impl IntoIterator<Item=T>)->(Self,Vec<usize>){let xs=xs.into_iter().collect::<Vec<_>>();let n=xs.len();if n==0{return(Self(Container::Empty),vec![]);}let min=*xs.iter().min().unwrap();let max=*xs.iter().max().unwrap();let mut ys=vec![0;xs.len()];if SMALL{let len=(max-min).cast()+1;let mut sum=vec![0;len+1];if DISTINCT{for&x in&xs{sum[(x-min).cast()+1]+=1;}for i in 0..len{sum[i+1]+=sum[i];}for i in 0..n{let j=(xs[i]-min).cast();ys[i]=sum[j]as usize;sum[j]+=1;}for i in(1..=len).rev(){sum[i]=sum[i-1];}sum[0]=0;(Self(Container::Small{min,sum}),ys)}else{for&x in&xs{sum[(x-min).cast()+1]=1;}for i in 0..len{sum[i+1]+=sum[i];}for i in 0..n{let j=(xs[i]-min).cast();ys[i]=sum[j]as usize;}(Self(Container::Small{min,sum}),ys)}}else if DISTINCT{let mut ord=(0..n).collect::<Vec<_>>();ord.sort_by_key(|&i|xs[i]);let mut new_xs=Vec::with_capacity(n);for i in 0..n{ys[ord[i]]=i;new_xs.push(xs[ord[i]]);}(Self(Container::Large{xs:new_xs}),ys)}else{let mut ord=(0..n).collect::<Vec<_>>();ord.sort_unstable_by_key(|&i|xs[i]);let mut new_xs=Vec::with_capacity(n);for i in 0..n{if i>0&&xs[ord[i]]==xs[ord[i-1]]{ys[ord[i]]=new_xs.len()-1;}else{ys[ord[i]]=new_xs.len();new_xs.push(xs[ord[i]]);}}new_xs.shrink_to_fit();(Self(Container::Large{xs:new_xs}),ys)}}pub fn encode(&self,x:T)->usize{match&self.0{Container::Empty=>0,Container::Small{min,sum,..}=>{let j=(x-*min).max(T::zero()).cast().min(sum.len()-1);sum[j]as usize}Container::Large{xs}=>xs.partition_point(|&xi|xi<x),}}pub fn decode(&self,i:usize)->T{match&self.0{Container::Empty=>panic!("out of range"),Container::Small{min,sum,..}=>*min+sum[i].cast(),Container::Large{xs}=>xs[i],}}}impl<T,const SMALL:bool,const DISTINCT:bool>CoordinateCompression<T,SMALL,DISTINCT>where T:Integer+Cast<usize>,u32:Cast<T>,{pub fn len(&self)->usize{match&self.0{Container::Empty=>0,Container::Small{sum,..}=>*sum.last().unwrap()as usize,Container::Large{xs}=>xs.len(),}}pub fn is_empty(&self)->bool{matches!(&self.0,Container::Empty)}}#[derive(Clone)]enum Container<T>{Empty,Small{min:T,sum:Vec<u32>},Large{xs:Vec<T>},}}
pub mod linear_sieve {use std::iter::FusedIterator;pub struct LinearSieve{n:u32,ps:Vec<u32>,lpf:Vec<u32>,}impl LinearSieve{pub fn new(n:usize)->Self{let sz=n/30*8+match n%30{29.. =>8,23.. =>7,19.. =>6,17.. =>5,13.. =>4,11.. =>3,7.. =>2,1.. =>1,_=>0,};let n=n as u32;let mut ps=vec![2,3,5];ps.retain(|&p|p<=n);let mut lpf=vec![1;sz];for i in 1..sz{let x=Self::x(i);if lpf[i]==1{lpf[i]=x;ps.push(x);}let lpf_i=lpf[i];for&y in ps.iter().skip(3).take_while(|&&y|y<=lpf_i&&x*y<=n){let j=Self::id(x*y).unwrap();lpf[j]=y;}}Self{n,ps,lpf}}pub fn is_prime(&self,x:usize)->bool{let x=x as u32;assert!(x<=self.n);match x{2|3|5=>true,_=>Self::id(x).map_or(false,|i|self.lpf[i]==x),}}pub fn primes(&self,)->impl Iterator<Item=usize>+FusedIterator+ExactSizeIterator+DoubleEndedIterator+'_{self.ps.iter().copied().map(|p|p as _)}pub fn least_factor(&self,x:usize)->Option<usize>{let x=x as u32;assert!(x<=self.n);match x{..=1=>None,_ if x%2==0=>Some(2),_ if x%3==0=>Some(3),_ if x%5==0=>Some(5),_=>Some(self.lpf[Self::id(x).unwrap()]as usize),}}pub fn factors(&self,mut x:usize)->impl Iterator<Item=usize>+'_{std::iter::from_fn(move||{let p=self.least_factor(x)?;x/=p;Some(p)})}fn id(x:u32)->Option<usize>{if x<=6{return None;}let offset=x/30*8;let res=match x%30{1=>0,7=>1,11=>2,13=>3,17=>4,19=>5,23=>6,29=>7,_=>return None,}+offset;Some(res as usize)}fn x(id:usize)->u32{const CANDS:[u32;8]=[1,7,11,13,17,19,23,29];id as u32/8*30+CANDS[id%8]}}}
}
pub(crate) mod macros {
pub mod __algebraic_traits_0_1_0 {pub use crate::{__cargo_equip_macro_def___algebraic_traits_0_1_0_define_act as define_act,__cargo_equip_macro_def___algebraic_traits_0_1_0_define_algebra as define_algebra};}
pub mod numeric_traits {}
pub mod wavelet_matrix {}
pub mod as_half_open_range {}
pub mod coordinate_compression {}
pub mod linear_sieve {}
}
pub(crate) mod prelude {pub use crate::__cargo_equip::crates::*;}
mod preludes {
pub mod __algebraic_traits_0_1_0 {}
pub mod numeric_traits {}
pub mod wavelet_matrix {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{__algebraic_traits_0_1_0 as algebraic_traits,as_half_open_range,coordinate_compression,numeric_traits};}
pub mod as_half_open_range {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::numeric_traits;}
pub mod coordinate_compression {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::numeric_traits;}
pub mod linear_sieve {}
}
}