MikuroXina’s gists

MikuroXina / seg_tree.rs

Last active May 11, 2024 10:01

The implementation of Segment Tree.

MikuroXina / chmax.rs

Created March 27, 2021 09:16

You can use with `impl` to the type you want.

	trait ChMax: Sized + PartialOrd {
	fn ch_max(&mut self, other: Self) {
	if *self < other {
	*self = other;
	}
	}
	}

MikuroXina / weighted_union_find.rs

Last active January 6, 2022 01:58

The weighted union find tree implementation.

	/// It represents parent if positive, size of tree if negative
	#[derive(Debug, Clone, Copy, PartialEq, PartialOrd)]
	struct UnionFindIndex(isize);

	impl UnionFindIndex {
	fn index(index: usize) -> Self {
	debug_assert!(index < (std::isize::MAX as usize));
	Self(index as isize)
	}

MikuroXina / gcd_ext.rs

Last active January 6, 2022 01:49

The implementation of Extended Euclidean algorithm.

	use num::{Integer, One, Zero};

	pub trait GcdNum: Copy + Integer + One + Zero + std::ops::SubAssign {}

	pub fn gcd_ext<T: GcdNum>(
	a: T,
	b: T,
	) -> (T, T) {
	fn inner<T: GcdNum>(
	a: T,

MikuroXina / lazy_seg_tree.rs

Last active February 16, 2025 18:49

The implementation of Lazy Eval Segmentation Tree.

MikuroXina / chebyshev_point.rs

Last active October 19, 2023 18:09

The chebyshev point implementation for calculating manhattan distance quickly.

	#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
	struct ChebyshevPoint(i64, i64);

	impl ChebyshevPoint {
	fn from_manhattan(x: i64, y: i64) -> Self {
	Self(x - y, x + y)
	}

	fn manhattan_dist(self, other: Self) -> u64 {
	self.0.abs_diff(other.0).max(self.1.abs_diff(other.1))

MikuroXina / binomial.rs

Last active February 18, 2025 00:46

The pre-calculator of binomial coefficients.

	/// A monoid with inverse and zero element.
	pub trait InvZeroMonoid: From<u64> + Copy + Sized {
	/// for all x; x.op(ZERO) == ZERO
	const ZERO: Self;
	/// for all x; x.op(ONE) == x
	const ONE: Self;

	/// for all x, y, z; x.op(y).op(z) == x.op(y.op(z))
	fn op(self, rhs: Self) -> Self;
	/// for all x; if x != ZERO then x.op(x.inv()) == ONE

MikuroXina / slope_trick.rs

Created June 2, 2021 02:02

The implementation of Slope Trick.

MikuroXina / digits.rs

Last active January 6, 2022 01:42

The iterator for digits of a number.

	pub struct Digits {
	num: u64,
	radix: u64,
	}

	impl Digits {
	pub fn new(num: u64, radix: u64) -> Self {
	assert!(0 < radix, "radix must be greater than zero");
	Self { num, radix }
	}

MikuroXina / mod_int.rs

Last active July 13, 2025 04:38

An integer mod n.

	use num::{One, Zero};

	/// An integer mod n.
	#[derive(Debug, Default, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
	pub struct ModInt<const MOD: u64>(u64);

	impl<const MOD: u64> ModInt<MOD> {
	pub fn as_u64(self) -> u64 {
	self.0
	}

Mikuroさいな MikuroXina