use std::ops::{ Add, Sub, Mul }; pub trait LineDecimal: Add + Sub + Mul + Copy + PartialOrd {} impl LineDecimal for i64 {} impl LineDecimal for f64 {} pub struct Line { pub a: T, pub b: T, } impl Line { pub fn new(a: T, b: T) -> Self { Line { a, b } } pub fn get(&self, x: T) -> T { self.a * x + self.b } } impl Clone for Line { fn clone(&self) -> Self { Line { a: self.a, b: self.b } } } use std::collections::VecDeque; pub struct MonotoneCHT { lines: VecDeque>, } impl MonotoneCHT { pub fn new() -> Self { MonotoneCHT { lines: VecDeque::new() } } fn check(ln0: &Line, ln1: &Line, ln2: &Line) -> bool { if ln0.a == ln1.a { ln0.b < ln1.b } else if ln1.a == ln2.a { ln1.b > ln2.b } else { (ln1.b - ln0.b) * (ln1.a - ln2.a) >= (ln2.b - ln1.b) * (ln0.a - ln1.a) } } pub fn push_front(&mut self, ln: Line) { while 1 < self.lines.len() && MonotoneCHT::check(&ln, &self.lines[0], &self.lines[1]) { self.lines.pop_front(); } self.lines.push_front(ln); } pub fn push_back(&mut self, ln: Line) { while 1 < self.lines.len() && MonotoneCHT::check(&self.lines[self.lines.len() - 2], &self.lines[self.lines.len() - 1], &ln) { self.lines.pop_back(); } self.lines.push_back(ln); } pub fn min_value(&self, x: T) -> T { let mut ok = 0; let mut ng = self.lines.len(); while ng - ok > 1 { let mid = (ok + ng) / 2; let ln0 = &self.lines[mid - 1]; let ln1 = &self.lines[mid]; if (ln1.b - ln0.b) <= x * (ln0.a - ln1.a) { ok = mid; } else { ng = mid; } } self.lines[ok].get(x) } pub fn incl_query(&self) -> MonotoneCHTInclQuery { MonotoneCHTInclQuery { lines: &self.lines, i: 0 } } pub fn deq_query(&self) -> MonotoneCHTDeqQuery { MonotoneCHTDeqQuery { lines: &self.lines, i: self.lines.len() - 1 } } } pub struct MonotoneCHTInclQuery<'a, T: LineDecimal> { lines: &'a VecDeque>, i: usize, } impl<'a, T: LineDecimal> MonotoneCHTInclQuery<'a, T> { pub fn min_value(&mut self, x: T) -> T { while self.i + 1 < self.lines.len() && self.lines[self.i].get(x) >= self.lines[self.i + 1].get(x) { self.i += 1; } self.lines[self.i].get(x) } } pub struct MonotoneCHTDeqQuery<'a, T: LineDecimal> { lines: &'a VecDeque>, i: usize, } impl<'a, T: LineDecimal> MonotoneCHTDeqQuery<'a, T> { pub fn min_value(&mut self, x: T) -> T { while self.i > 0 && self.lines[self.i].get(x) >= self.lines[self.i - 1].get(x) { self.i -= 1; } self.lines[self.i].get(x) } } /// Reading from standard input /// /// `input!` is useful for competition programming. /// There are some forms. /// /// - Tuple /// /// ``` /// use cp_rust_library::*; /// input! { source = "2 3", ab: (usize, usize), } /// assert_eq!(ab.0, 2); /// assert_eq!(ab.1, 3); /// ``` /// /// - Array /// ``` /// use cp_rust_library::*; /// input! { source = "1 2 3 4", a: [usize; 4], } /// assert_eq!(a, vec![1, 2, 3, 4]); /// ``` /// /// - String -> Vec /// ``` /// use cp_rust_library::*; /// input! { source = "qwerty", s: chars, } /// assert_eq!('q', s[0]); /// ``` /// /// - Other /// ``` /// use cp_rust_library::*; /// input! { source = "123", a: usize, } /// assert_eq!(123, a); /// ``` /// /// This macro will use parse::<$type>() to parse string. #[macro_export] macro_rules! input { (source = $s:expr, $($r:tt)*) => { let mut iter = $s.split_whitespace(); input_rec!{ iter, $($r)* } }; ($($r:tt)*) => { let s = { use std::io::Read; let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); s }; let mut iter = s.split_whitespace(); input_rec!{ iter, $($r)* } }; } #[macro_export] macro_rules! input_rec { ($iter:expr) => {}; ($iter:expr, ) => {}; ($iter:expr, $var:ident : $t:tt, $($r:tt)*) => { let $var = read_value!($iter, $t); input_rec! { $iter, $($r)* } }; } #[macro_export] macro_rules! read_value { // tuple ($iter:expr, ( $($t:tt), * )) => { ( $(read_value!($iter, $t)), * ) }; // array ($iter:expr, [ $t:tt; $len:expr ]) => { (0..$len).map(|_| { read_value!($iter, $t) }).collect::>() }; // string ($iter:expr, chars) => { read_value!($iter, String).chars().collect::>() }; // any other ($iter:expr, $t:ty) => { $iter.next().unwrap().parse::<$t>().expect("Parse error") }; } fn rec(l: usize, r: usize, s: &Vec, ans: &mut Vec) { if r <= l { return; } let m = (l + r) / 2; rec(l, m, s, ans); rec(m + 1, r, s, ans); println!("{:?}", (l, m)); { let mut cht = MonotoneCHT::new(); for ri in m+1..r+1 { let rr = ri as i64; cht.push_back(Line::new(-2i64 * rr, rr * rr + s[0] - s[ri])); } let mut qry = cht.incl_query(); let mut now = 1e18 as i64; for i in l..m { let ii = i as i64; now = std::cmp::min(now, qry.min_value(ii) + ii * ii - s[0] + s[i]); ans[i] = std::cmp::min(ans[i], now); } } println!("{:?}", (m, r)); { let mut cht = MonotoneCHT::new(); for li in l..m+1 { let ll = li as i64; cht.push_back(Line::new(-2i64 * ll, ll * ll - s[0] + s[li])); } let mut qry = cht.deq_query(); let mut now = 1e18 as i64; for i in (m+1..r+1).rev() { let ii = i as i64; now = std::cmp::min(now, qry.min_value(ii) + ii * ii + s[0] - s[i]); ans[i - 1] = std::cmp::min(ans[i - 1], now); } } } fn main() { input! { n: usize, a: [i64; n], } let mut s = a; s.push(0); for i in (0..n).rev() { s[i] += s[i + 1]; } let mut ans = vec![0i64; n]; for i in 0..n { ans[i] = 1 + s[i] - s[i + 1]; } rec(0, n, &s, &mut ans); for i in 0..n { println!("{}", ans[i]); } }