MikuroXina

pub fn inversions(nums: &[usize]) -> Vec<usize> {
    let len = nums.len();
    let mut counts = SegTree::<Sum>::new(len);
    let mut inversions = Vec::with_capacity(len);
    for (i, &num) in nums.into_iter().enumerate() {
        let Sum(inv) = counts.query(0..num);
        inversions.push(i - inv);
        counts.insert(num, Sum(1));
    }
    inversions

MikuroXina

pub fn longest_increasing_subsequence<T: Ord>(nums: impl IntoIterator<Item = T>) -> Vec<usize> {
    let mut nums = nums.into_iter();
    let Some(first) = nums.next() else {
        return vec![];
    };
    let mut len_by_using = vec![1];
    let mut sorted = vec![first];
    for num in nums {
        let lower_bound = sorted.binary_search(&num).unwrap_or_else(|idx| idx);
        if lower_bound == sorted.len() {

MikuroXina

#[inline]
pub fn merge<T, L, R>(left: L, right: R) -> Merge<T, L::IntoIter, R::IntoIter>
where
    T: PartialOrd,
    L: IntoIterator<Item = T>,
    R: IntoIterator<Item = T>,
{
    Merge {
        left: left.into_iter().peekable(),
        right: right.into_iter().peekable(),

MikuroXina

pub fn strongly_connected_components(graph: &[Vec<usize>]) -> Vec<Vec<usize>> {
    let vertexes = graph.len();
    let inv_graph = {
        let mut inv_graph = vec![vec![]; vertexes];
        for (from, adj) in graph.into_iter().enumerate() {
            for &to in adj {
                inv_graph[to].push(from);
            }
        }
        inv_graph

MikuroXina

use std::collections::HashSet;

/// Monoid must satisfy:
/// ```rs
/// fn test<M: Monoid>(m: M, n: M, l: M) {
///   assert_eq!(m.op(M::ID), m);
///   assert_eq!(M::ID.op(m), m);
///   assert_eq!(m.op(n.op(l)), m.op(n).op(l));
/// }
/// ```

MikuroXina

#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct Field {
    // both of width and height must ≤ i64::MAX for safety
    width: u64,
    height: u64,
}

impl Field {
    pub fn new(width: u64, height: u64) -> Self {
        assert!(

MikuroXina

#[derive(Clone, PartialEq, Eq, Hash)]
struct Poly<const W: usize, const H: usize> {
    field: [[bool; W]; H],
}

impl<const W: usize, const H: usize> std::fmt::Debug for Poly<W, H> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        writeln!(f, "\"\"\"")?;
        for y in 0..H {
            for x in 0..W {

MikuroXina

/// Coordinate on 2D plane, which `+X` is right and `+Y` is down.
#[derive(Debug, Default, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct Coordinate {
    pub x: usize,
    pub y: usize,
}

#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub struct GridGraph<T> {
    grid: Vec<Vec<T>>,

MikuroXina

class SelfLoveRecoveryProgram:
    def __init__(self):
        self.self_love_level = 50

    def increase_self_love(self, amount):
        self.self_love_level += amount

    def decrease_self_love(self, amount):
        self.self_love_level -= amount

MikuroXina

use std::collections::BTreeMap;

#[derive(Debug)]
pub struct CoCo<K: Ord> {
    forward: BTreeMap<K, usize>,
    backward: Vec<K>,
}

impl<K: Ord> CoCo<K> {
    pub const fn new() -> Self {