use std::{iter::repeat_with, ops::Range, usize::MAX}; #[allow(unused_imports)] #[cfg(feature = "dbg")] use dbg::lg; use wavelet_matrix::WaveletMatrix; fn main() { let mut buf = ngtio::with_stdin(); let n = buf.usize(); let k = buf.usize(); let (wm, table) = WaveletMatrix::from_iter_collect_vec2(repeat_with(|| buf.usize()).take(n)); let cum = table .into_iter() .map(|mut row| { row.insert(0, 0); accum::add(&mut row); row }) .collect::>(); let mut ans = MAX; for (l, r) in (0..).zip(k..).take_while(|&(_, r)| r <= n) { let med = wm.quantile(k / 2, l..r, ..).unwrap(); let calc_sum = |range: Range| { wm.spans(l..r, range) .map(|span| { let Range { start, end } = span.index; cum[span.depth][end] - cum[span.depth][start] }) .sum::() }; let lsum = calc_sum(0..med); let rsum = calc_sum(med..MAX); let lsize = wm.range_freq(l..r, ..med); let rsize = wm.range_freq(l..r, med..); let cost = lsize * med - lsum + rsum - rsize * med; ans = ans.min(cost); } println!("{}", ans); } // accum {{{ #[allow(dead_code)] mod accum { use std::{ cmp::Ord, ops::{ AddAssign, BitAndAssign, BitOrAssign, BitXorAssign, DivAssign, MulAssign, SubAssign, }, }; pub fn add(a: &mut [T]) { for_each_mut(a, |&mut x, y| *y += x); } pub fn add_inv(a: &mut [T]) { rfor_each_mut(a, |&mut x, y| *y -= x); } pub fn mul(a: &mut [T]) { for_each_mut(a, |&mut x, y| *y *= x); } pub fn mul_inv(a: &mut [T]) { rfor_each_mut(a, |&mut x, y| *y /= x); } // -- ord pub fn min(a: &mut [T]) { for_each_mut(a, |&mut x, y| *y = x.min(*y)); } pub fn max(a: &mut [T]) { for_each_mut(a, |&mut x, y| *y = x.max(*y)); } pub fn skipped_min(a: &[T], max: T) -> Vec { skipped(a, |x, y| (*x).min(*y), || max).collect() } pub fn skipped_max(a: &[T], min: T) -> Vec { skipped(a, |x, y| (*x).max(*y), || min).collect() } // -- bit pub fn xor(a: &mut [T]) { for_each_mut(a, |&mut x, y| *y ^= x); } pub fn xor_inv(a: &mut [T]) { rfor_each_mut(a, |&mut x, y| *y ^= x); } pub fn or(a: &mut [T]) { for_each_mut(a, |&mut x, y| *y |= x); } pub fn and(a: &mut [T]) { for_each_mut(a, |&mut x, y| *y &= x); } // -- for_each pub fn for_each(a: &[T], mut f: impl FnMut(&T, &T)) { if !a.is_empty() { for i in 1..a.len() { let (left, right) = a.split_at(i); f(left.last().unwrap(), right.first().unwrap()); } } } pub fn rfor_each(a: &[T], mut f: impl FnMut(&T, &T)) { if !a.is_empty() { for i in (1..a.len()).rev() { let (left, right) = a.split_at(i); f(left.last().unwrap(), right.first().unwrap()); } } } pub fn for_each_mut(a: &mut [T], mut f: impl FnMut(&mut T, &mut T)) { if !a.is_empty() { for i in 1..a.len() { let (left, right) = a.split_at_mut(i); f(left.last_mut().unwrap(), right.first_mut().unwrap()); } } } pub fn rfor_each_mut(a: &mut [T], mut f: impl FnMut(&mut T, &mut T)) { if !a.is_empty() { for i in (1..a.len()).rev() { let (left, right) = a.split_at_mut(i); f(left.last_mut().unwrap(), right.first_mut().unwrap()); } } } pub fn skipped(a: &[T], f: F, identity: I) -> Skipped where F: FnMut(&T, &T) -> T, I: FnMut() -> T, { Skipped::new(a, f, identity) } #[derive(Clone, Debug, Default, Hash, PartialEq)] pub struct Skipped<'a, T, F, I> { a: &'a [T], left: T, right: Vec, f: F, identity: I, } impl<'a, T, F, I> Skipped<'a, T, F, I> where F: FnMut(&T, &T) -> T, I: FnMut() -> T, { fn new(a: &'a [T], mut f: F, mut identity: I) -> Self { let right = if a.is_empty() { Default::default() } else { let mut right = vec![identity()]; for x in a[1..].iter().rev() { let x = f(x, right.last().unwrap()); right.push(x); } right }; Self { a, left: identity(), right, f, identity, } } } impl<'a, T, F, I> Iterator for Skipped<'a, T, F, I> where F: FnMut(&T, &T) -> T, I: FnMut() -> T, { type Item = T; fn next(&mut self) -> Option { if let Some(right) = self.right.pop() { let res = (self.f)(&self.left, &right); self.left = (self.f)(&self.left, &self.a[0]); self.a = &self.a[1..]; Some(res) } else { None } } } } // }}} // wavelet_matrix {{{ #[allow(dead_code)] mod wavelet_matrix { #![allow(clippy::len_zero)] use std::{ fmt::Debug, iter::FromIterator, mem::size_of, ops::{Bound, Range, RangeBounds}, }; const UNIT: usize = size_of::(); #[derive(Clone, Default, Hash, PartialEq)] pub struct WaveletMatrix { table: Vec, } impl Debug for WaveletMatrix { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { f.debug_list() .entries((0..self.len()).map(|i| self.access(i))) .finish() } } impl FromIterator for WaveletMatrix { fn from_iter>(iter: I) -> Self { let mut slice = iter.into_iter().map(Into::into).collect::>(); Self::from_slice_of_usize_mut(&mut slice, |_| ()) } } impl WaveletMatrix { pub fn is_empty(&self) -> bool { self.table.is_empty() } pub fn len(&self) -> usize { self.table.first().map_or(0, |row| row.len()) } pub fn lim(&self) -> usize { 1 << self.table.len() } pub fn from_iter_collect_vec2( iter: impl IntoIterator, ) -> (Self, Vec>) { let mut slice = iter.into_iter().map(Into::into).collect::>(); let mut table = Vec::new(); let wm = Self::from_slice_of_usize_mut(&mut slice, |row| table.push(row.to_vec())); (wm, table) } pub fn from_slice_of_usize_mut( slice: &mut [usize], mut callback: impl FnMut(&[usize]), ) -> Self { let ht = slice.iter().copied().max().map_or(0, |value| { (value + 1).next_power_of_two().trailing_zeros() as usize }); let table = (0..ht) .rev() .map(|p| { callback(slice); let res = slice.iter().map(|&value| value >> p & 1 == 1).collect(); stable_partition_by_key(slice, |value| value >> p & 1 == 1); res }) .collect(); callback(slice); Self { table } } pub fn access(&self, mut i: usize) -> usize { assert!(i < self.table[0].len()); let mut ans = 0; for row in &self.table { let here = row.access(i); i = next_position(row, i, row.access(i)); ans <<= 1; ans |= here as usize; } ans } pub fn range_freq( &self, index: impl RangeBounds, value: impl RangeBounds, ) -> usize { self.spans(index, value).map(|span| span.index.len()).sum() } pub fn next_value( &self, index: impl RangeBounds, value: impl RangeBounds, ) -> Option { self.root(open(index, self.len())) .next_value(&open(value, self.lim())) } pub fn prev_value( &self, index: impl RangeBounds, value: impl RangeBounds, ) -> Option { self.root(open(index, self.len())) .prev_value(&open(value, self.lim())) } pub fn quantile( &self, k: usize, index: impl RangeBounds, value: impl RangeBounds, ) -> Option { self.root(open(index, self.len())) .quantile(k, &open(value, self.lim())) .ok() } pub fn spans( &self, index: impl RangeBounds, value: impl RangeBounds, ) -> Spans<'_> { let index = open(index, self.len()); let target = open(value, self.lim()); if target.len() == 0 { return Spans { stack: Vec::new(), target, }; } let mut current = self.root(index); let mut stack = Vec::new(); while !is_subrange_of(¤t.value, &target) { let left = current.left_down(); if is_disjoint_with(&left.value, &target) { current = current.right_down(); } else { stack.push(current); current = left; } } stack.push(current); Spans { stack, target } } fn root(&self, index: Range) -> SpanInNode<'_> { SpanInNode { wm: self, depth: 0, index, value: 0..self.lim(), } } } fn stable_partition_by_key(slice: &mut [usize], is_upper: impl Fn(usize) -> bool) -> usize { let mut upper = Vec::new(); let mut i = 0; for j in 0..slice.len() { if is_upper(slice[j]) { upper.push(slice[j]); } else { slice[i] = slice[j]; i += 1; } } slice[i..].copy_from_slice(&upper); i } fn next_position(row: &StaticBitVec, i: usize, which: bool) -> usize { match which { false => i - row.rank(i), true => row.len() - row.rank(row.len()) + row.rank(i), } } fn next_position_range(row: &StaticBitVec, range: &Range, which: bool) -> Range { next_position(row, range.start, which)..next_position(row, range.end, which) } #[derive(Clone, Debug, Default, Hash, PartialEq)] pub struct StaticBitVec { len: usize, rank: Vec, pattern: Vec, } impl FromIterator for StaticBitVec { fn from_iter>(iter: T) -> Self { let mut iter = iter.into_iter(); let mut rank = Vec::new(); let mut pattern = Vec::new(); let mut rank_c = 0; let mut pattern_c = 0; let mut len = 0; 'OUTER: loop { rank.push(rank_c); for i in 0..UNIT { match iter.next() { None => { pattern.push(pattern_c); break 'OUTER; } Some(false) => (), Some(true) => { pattern_c |= 1 << i; rank_c += 1; } } len += 1; } pattern.push(pattern_c); pattern_c = 0; } Self { len, rank, pattern } } } impl StaticBitVec { pub fn is_empty(&self) -> bool { self.len == 0 } pub fn len(&self) -> usize { self.len } pub fn access(&self, i: usize) -> bool { assert!(i < self.len); let (q, r) = divrem(i, UNIT); self.pattern[q] >> r & 1 == 1 } pub fn rank(&self, end: usize) -> usize { assert!(end <= self.len); let (q, r) = divrem(end, UNIT); self.rank[q] + (self.pattern[q] & ((1 << r) - 1)).count_ones() as usize } pub fn select(&self, target: usize) -> usize { if target == 0 { return 0; } let mut lr = 0..self.rank.len(); while 1 < lr.len() { let c = midpoint(&lr); *if self.rank[c] < target { &mut lr.start } else { &mut lr.end } = c; } let q = lr.start; let mut lr = 0..UNIT; while 1 < lr.len() { let c = midpoint(&lr); *if (self.rank[q] + (self.pattern[q] & ((1 << c) - 1)).count_ones() as usize) < target { &mut lr.start } else { &mut lr.end } = c; } q * UNIT + lr.end } } #[derive(Clone, Debug, Hash, PartialEq)] pub struct Spans<'a> { stack: Vec>, target: Range, } impl<'a> Iterator for Spans<'a> { type Item = SpanInNode<'a>; fn next(&mut self) -> Option { let ans = self.stack.pop()?; if ans.value.end == self.target.end { self.stack.clear(); } else { let prev = self.stack.pop().unwrap(); let mut next = prev.right_down(); self.stack.push(next.clone()); while !is_subrange_of(&next.value, &self.target) { next = next.left_down(); self.stack.push(next.clone()); } } Some(ans) } } #[derive(Clone, Debug, Hash, PartialEq)] pub struct SpanInNode<'a> { wm: &'a WaveletMatrix, pub depth: usize, pub index: Range, pub value: Range, } impl<'a> SpanInNode<'a> { fn left_down(&self) -> Self { Self { wm: self.wm, depth: self.depth + 1, index: next_position_range(&self.wm.table[self.depth], &self.index, false), value: self.value.start..midpoint(&self.value), } } fn right_down(&self) -> Self { Self { wm: self.wm, depth: self.depth + 1, index: next_position_range(&self.wm.table[self.depth], &self.index, true), value: midpoint(&self.value)..self.value.end, } } fn range_freq(&self, target: &Range) -> usize { if is_disjoint_with(&self.value, target) || self.index.len() == 0 { 0 } else if is_subrange_of(&self.value, target) { self.index.len() } else { self.left_down().range_freq(target) + self.right_down().range_freq(target) } } fn next_value(&self, target: &Range) -> Option { if is_disjoint_with(&self.value, target) || self.index.len() == 0 { None } else if self.value.len() == 1 { Some(self.value.start) } else { self.left_down() .next_value(target) .or_else(|| self.right_down().next_value(target)) } } fn prev_value(&self, target: &Range) -> Option { if is_disjoint_with(&self.value, target) || self.index.len() == 0 { None } else if self.value.len() == 1 { Some(self.value.start) } else { self.right_down() .prev_value(target) .or_else(|| self.left_down().prev_value(target)) } } fn quantile(&self, k: usize, target: &Range) -> Result { let ans = if is_disjoint_with(&self.value, target) { Err(0) } else if is_subrange_of(&self.value, target) && self.index.len() <= k { Err(self.index.len()) } else if self.value.len() == 1 { Ok(self.value.start) } else { self.left_down().quantile(k, target).or_else(|len| { self.right_down() .quantile(k - len, target) .map_err(|e| e + len) }) }; ans } } fn midpoint(range: &Range) -> usize { range.start + (range.end - range.start) / 2 } fn is_disjoint_with(lhs: &Range, rhs: &Range) -> bool { lhs.end <= rhs.start || rhs.end <= lhs.start } fn is_subrange_of(lhs: &Range, rhs: &Range) -> bool { rhs.start <= lhs.start && lhs.end <= rhs.end } fn divrem(num: usize, den: usize) -> (usize, usize) { let q = num / den; (q, num - q * den) } fn open(range: impl RangeBounds, len: usize) -> Range { (match range.start_bound() { Bound::Included(&l) => l.min(len), Bound::Excluded(&l) => (l + 1).min(len), Bound::Unbounded => 0, })..(match range.end_bound() { Bound::Included(&r) => (r + 1).min(len), Bound::Excluded(&r) => r.min(len), Bound::Unbounded => len, }) } } // }}} // template {{{ #[cfg(not(feature = "dbg"))] #[allow(unused_macros)] #[macro_export] macro_rules! lg { ($($expr:expr),*) => {}; } #[allow(dead_code)] mod ngtio { mod i { pub use self::{ multi_token::{Leaf, Parser, ParserTuple, RawTuple, Tuple, VecLen}, token::{Token, Usize1}, }; use std::{ io::{self, BufRead}, iter, }; pub fn with_stdin() -> Tokenizer> { io::BufReader::new(io::stdin()).tokenizer() } pub fn with_str(src: &str) -> Tokenizer<&[u8]> { src.as_bytes().tokenizer() } pub struct Tokenizer { queue: Vec, // FIXME: String のみにすると速そうです。 scanner: S, } macro_rules! prim_method { ($name:ident: $T:ty) => { pub fn $name(&mut self) -> $T { <$T>::leaf().parse(self) } }; ($name:ident) => { prim_method!($name: $name); }; } macro_rules! prim_methods { ($name:ident: $T:ty; $($rest:tt)*) => { prim_method!($name:$T); prim_methods!($($rest)*); }; ($name:ident; $($rest:tt)*) => { prim_method!($name); prim_methods!($($rest)*); }; () => () } impl Tokenizer { pub fn token(&mut self) -> String { self.load(); self.queue.pop().expect("入力が終了したのですが。") } pub fn new(scanner: S) -> Self { Self { queue: Vec::new(), scanner, } } fn load(&mut self) { while self.queue.is_empty() { let mut s = String::new(); let length = self.scanner.read_line(&mut s).unwrap(); // 入力が UTF-8 でないときにエラーだそうです。 if length == 0 { break; } self.queue = s.split_whitespace().rev().map(str::to_owned).collect(); } } pub fn skip_line(&mut self) { assert!( self.queue.is_empty(), "行の途中で呼ばないでいただきたいです。現在のトークンキュー: {:?}", &self.queue ); self.load(); } pub fn end(&mut self) { self.load(); assert!(self.queue.is_empty(), "入力はまだあります!"); } pub fn parse(&mut self) -> T::Output { T::parse(&self.token()) } pub fn parse_collect(&mut self, n: usize) -> B where B: iter::FromIterator, { iter::repeat_with(|| self.parse::()).take(n).collect() } pub fn tuple(&mut self) -> ::Output { T::leaf_tuple().parse(self) } pub fn vec(&mut self, len: usize) -> Vec { T::leaf().vec(len).parse(self) } pub fn vec_tuple( &mut self, len: usize, ) -> Vec<::Output> { T::leaf_tuple().vec(len).parse(self) } pub fn vec2(&mut self, height: usize, width: usize) -> Vec> { T::leaf().vec(width).vec(height).parse(self) } pub fn vec2_tuple( &mut self, height: usize, width: usize, ) -> Vec::Output>> where T: RawTuple, { T::leaf_tuple().vec(width).vec(height).parse(self) } prim_methods! { u8; u16; u32; u64; u128; usize; i8; i16; i32; i64; i128; isize; f32; f64; char; string: String; } } mod token { use super::multi_token::Leaf; use std::{any, fmt, marker, str}; pub trait Token: Sized { type Output; fn parse(s: &str) -> Self::Output; fn leaf() -> Leaf { Leaf(marker::PhantomData) } } impl Token for T where T: str::FromStr, ::Err: fmt::Debug, { type Output = Self; fn parse(s: &str) -> Self::Output { s.parse().unwrap_or_else(|_| { panic!("Parse error!: ({}: {})", s, any::type_name::(),) }) } } pub struct Usize1 {} impl Token for Usize1 { type Output = usize; fn parse(s: &str) -> Self::Output { usize::parse(s) .checked_sub(1) .expect("Parse error! (Zero substruction error of Usize1)") } } } mod multi_token { use super::{Token, Tokenizer}; use std::{io::BufRead, iter, marker}; pub trait Parser: Sized { type Output; fn parse(&self, server: &mut Tokenizer) -> Self::Output; fn vec(self, len: usize) -> VecLen { VecLen { len, elem: self } } } pub struct Leaf(pub(super) marker::PhantomData); impl Parser for Leaf { type Output = T::Output; fn parse(&self, server: &mut Tokenizer) -> T::Output { server.parse::() } } pub struct VecLen { pub len: usize, pub elem: T, } impl Parser for VecLen { type Output = Vec; fn parse(&self, server: &mut Tokenizer) -> Self::Output { iter::repeat_with(|| self.elem.parse(server)) .take(self.len) .collect() } } pub trait RawTuple { type LeafTuple: Parser; fn leaf_tuple() -> Self::LeafTuple; } pub trait ParserTuple { type Tuple: Parser; fn tuple(self) -> Self::Tuple; } pub struct Tuple(pub T); macro_rules! impl_tuple { ($($t:ident: $T:ident),*) => { impl<$($T),*> Parser for Tuple<($($T,)*)> where $($T: Parser,)* { type Output = ($($T::Output,)*); #[allow(unused_variables)] fn parse(&self, server: &mut Tokenizer) -> Self::Output { match self { Tuple(($($t,)*)) => { ($($t.parse(server),)*) } } } } impl<$($T: Token),*> RawTuple for ($($T,)*) { type LeafTuple = Tuple<($(Leaf<$T>,)*)>; fn leaf_tuple() -> Self::LeafTuple { Tuple(($($T::leaf(),)*)) } } impl<$($T: Parser),*> ParserTuple for ($($T,)*) { type Tuple = Tuple<($($T,)*)>; fn tuple(self) -> Self::Tuple { Tuple(self) } } }; } impl_tuple!(); impl_tuple!(t1: T1); impl_tuple!(t1: T1, t2: T2); impl_tuple!(t1: T1, t2: T2, t3: T3); impl_tuple!(t1: T1, t2: T2, t3: T3, t4: T4); impl_tuple!(t1: T1, t2: T2, t3: T3, t4: T4, t5: T5); impl_tuple!(t1: T1, t2: T2, t3: T3, t4: T4, t5: T5, t6: T6); impl_tuple!(t1: T1, t2: T2, t3: T3, t4: T4, t5: T5, t6: T6, t7: T7); impl_tuple!( t1: T1, t2: T2, t3: T3, t4: T4, t5: T5, t6: T6, t7: T7, t8: T8 ); } trait Scanner: BufRead + Sized { fn tokenizer(self) -> Tokenizer { Tokenizer::new(self) } } impl Scanner for R {} } pub use self::i::{with_stdin, with_str}; mod prelude { pub use super::i::{Parser, ParserTuple, RawTuple, Token, Usize1}; } } // }}}