beats.rs

trait ChminMaxSumLayout {
	fn get(&self, i: usize) -> (i32, i32, u32, i64);
	fn get_mut(&mut self, i: usize) -> (&mut i32, &mut i32, &mut u32, &mut i64);
}
struct ChminMaxSum<Layout>(Beats, Layout);
impl<Layout: ChminMaxSumLayout> ChminMaxSum<Layout> {
	fn add_range<C: ChminMaxSumLayout>(ctx: &mut C, i: usize, x: i32) {
		todo!();
	}
	fn push<C: ChminMaxSumLayout>(ctx: &mut C, i: usize, _len: usize) {
		todo!();
	}
	fn pull<C: ChminMaxSumLayout>(ctx: &mut C, i: usize) {
		todo!();
	}
	fn chmin(&mut self, l: usize, r: usize, x: i32) {
		self.0.update(
			&mut self.1,
			l,
			r,
			&mut |_layout, _i, _len| {
				if todo!() {
					true // covered
				} else {
					false // subtree walk
				}
			},
			&mut Self::push,
			&mut Self::pull,
		);
	}
	fn max(&mut self, l: usize, r: usize) -> i32 {
		self.0.query(
			&mut self.1,
			l,
			r,
			&mut Self::push,
			|layout, i| layout.get(i).0,
			|a, b| a.max(b),
		)
	}
	fn sum(&mut self, l: usize, r: usize) -> i64 {
		self.0.query(
			&mut self.1,
			l,
			r,
			&mut Self::push,
			|layout, i| layout.get(i).3,
			|a, b| a + b,
		)
	}
}

struct Layout {
	msc: Vec<(i32, i32, u32)>,
	sum: Vec<i64>,
}

impl Layout {
	fn build(n: usize, a: impl Iterator<Item = i32>) -> ChminMaxSum<Self> {
		let beats = Beats::new(n);
		ChminMaxSum(beats, todo!())
	}
}

impl ChminMaxSumLayout for Layout {
	fn get(&self, i: usize) -> (i32, i32, u32, i64) {
		let (max, second, count) = unsafe { *self.msc.get_unchecked(i) };
		(max, second, count, unsafe { *self.sum.get_unchecked(i) })
	}
	fn get_mut(&mut self, i: usize) -> (&mut i32, &mut i32, &mut u32, &mut i64) {
		let (max, second, count) = unsafe { self.msc.get_unchecked_mut(i) };
		(max, second, count, unsafe { self.sum.get_unchecked_mut(i) })
	}
}

struct Beats {
	cap: usize,
	h: u32,
}

impl Beats {
	fn new(n: usize) -> Self {
		let cap = n.next_power_of_two();
		let h = cap.trailing_zeros();
		Self { cap, h }
	}
	fn push_range<C, Push: FnMut(&mut C, usize, usize)>(
		&self,
		ctx: &mut C,
		l: usize,
		r_incl: usize,
		push: &mut Push,
	) {
		let mut len = self.cap;
		if l == r_incl {
			for d in (1..=self.h).rev() {
				push(ctx, l >> d, len);
				len >>= 1;
			}
			return;
		}
		let j = (l ^ r_incl).ilog2();
		for d in (j + 1..=self.h).rev() {
			push(ctx, l >> d, len);
			len >>= 1;
		}
		for d in (1..=j).rev() {
			push(ctx, l >> d, len);
			push(ctx, r_incl >> d, len);
			len >>= 1;
		}
	}
	fn apply_at<
		C,
		TryApply: FnMut(&mut C, usize, usize) -> bool,
		Push: FnMut(&mut C, usize, usize),
		Pull: FnMut(&mut C, usize),
	>(
		&self,
		ctx: &mut C,
		i: usize,
		len: usize,
		try_apply: &mut TryApply,
		push: &mut Push,
		pull: &mut Pull,
	) {
		if try_apply(ctx, i, len) {
			return;
		}
		push(ctx, i, len);
		self.apply_at(ctx, i << 1, len >> 1, try_apply, push, pull);
		self.apply_at(ctx, i << 1 | 1, len >> 1, try_apply, push, pull);
		pull(ctx, i);
	}
	fn update<
		C,
		TryApply: FnMut(&mut C, usize, usize) -> bool,
		Push: FnMut(&mut C, usize, usize),
		Pull: FnMut(&mut C, usize),
	>(
		&self,
		ctx: &mut C,
		l: usize,
		r: usize,
		try_apply: &mut TryApply,
		push: &mut Push,
		pull: &mut Pull,
	) {
		let mut l = l + self.cap;
		let mut r = r - 1 + self.cap;
		self.push_range(ctx, l, r, push);
		self.apply_at(ctx, l, 1, try_apply, push, pull);
		if l != r {
			self.apply_at(ctx, r, 1, try_apply, push, pull);
		}
		let mut len = 1;
		while (l >> 1) < (r >> 1) {
			if (l & 1) == 0 {
				self.apply_at(ctx, l + 1, len, try_apply, push, pull);
			}
			l >>= 1;
			pull(ctx, l);
			if (r & 1) == 1 {
				self.apply_at(ctx, r - 1, len, try_apply, push, pull);
			}
			r >>= 1;
			pull(ctx, r);
			len <<= 1;
		}
		while l > 1 {
			l >>= 1;
			pull(ctx, l);
		}
	}
	fn query<
		C,
		T,
		Push: FnMut(&mut C, usize, usize),
		Extract: FnMut(&mut C, usize) -> T,
		Combine: FnMut(T, T) -> T,
	>(
		&self,
		ctx: &mut C,
		l: usize,
		r: usize,
		push: &mut Push,
		mut extract: Extract,
		mut combine: Combine,
	) -> T {
		let mut l = l + self.cap;
		let mut r = r - 1 + self.cap;
		self.push_range(ctx, l, r, push);
		if l == r {
			return extract(ctx, l);
		}
		let mut lv = extract(ctx, l);
		let mut rv = extract(ctx, r);
		while (l >> 1) < (r >> 1) {
			if l & 1 == 0 {
				lv = combine(lv, extract(ctx, l + 1));
			}
			if r & 1 == 1 {
				rv = combine(extract(ctx, r - 1), rv);
			}
			l >>= 1;
			r >>= 1;
		}
		combine(lv, rv)
	}
}

usage.rs

fn main {
	let a = vec![0, 1, 2, 3];
	let mut tree = Layout::build(a.len(), a.into_iter());
	tree.chmin(0, 3, 1);
	println!("{}", tree.max(0, 4));
	println!("{}", tree.sum(2, 4));
}