use std::io::{Write, BufWriter}; // https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 macro_rules! input { ($($r:tt)*) => { let stdin = std::io::stdin(); let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock())); let mut next = move || -> String{ bytes.by_ref().map(|r|r.unwrap() as char) .skip_while(|c|c.is_whitespace()) .take_while(|c|!c.is_whitespace()) .collect() }; input_inner!{next, $($r)*} }; } macro_rules! input_inner { ($next:expr) => {}; ($next:expr,) => {}; ($next:expr, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($next, $t); input_inner!{$next $($r)*} }; } macro_rules! read_value { ($next:expr, ( $($t:tt),* )) => { ($(read_value!($next, $t)),*) }; ($next:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($next, $t)).collect::>() }; ($next:expr, usize1) => (read_value!($next, usize) - 1); ($next:expr, $t:ty) => ($next().parse::<$t>().expect("Parse error")); } /** * Lazy Segment Tree. This data structure is useful for fast folding and updating on intervals of an array * whose elements are elements of monoid T. Note that constructing this tree requires the identity * element of T and the operation of T. This is monomorphised, because of efficiency. T := i64, biop = max, upop = (+) * Reference: http://d.hatena.ne.jp/kyuridenamida/20121114/1352835261 * Verified by https://codeforces.com/contest/1114/submission/49759034 */ pub trait ActionRing { type T: Clone + Copy; // data type U: Clone + Copy + PartialEq + Eq; // action fn biop(x: Self::T, y: Self::T) -> Self::T; fn update(x: Self::T, a: Self::U, height: usize) -> Self::T; fn upop(fst: Self::U, snd: Self::U) -> Self::U; fn e() -> Self::T; fn upe() -> Self::U; // identity for upop } pub struct LazySegTree { n: usize, dep: usize, dat: Vec, lazy: Vec, } impl LazySegTree { #[allow(unused)] pub fn new(n_: usize) -> Self { let mut n = 1; let mut dep = 0; while n < n_ { n *= 2; dep += 1; } // n is a power of 2 LazySegTree { n: n, dep: dep, dat: vec![R::e(); 2 * n - 1], lazy: vec![R::upe(); 2 * n - 1] } } #[allow(unused)] pub fn with(a: &[R::T]) -> Self { let n_ = a.len(); let mut n = 1; let mut dep = 0; while n < n_ { n *= 2; dep += 1; } // n is a power of 2 let mut dat = vec![R::e(); 2 * n - 1]; for i in 0..n_ { dat[n - 1 + i] = a[i]; } for i in (0..n - 1).rev() { dat[i] = R::biop(dat[2 * i + 1], dat[2 * i + 2]); } LazySegTree { n: n, dep: dep, dat: dat, lazy: vec![R::upe(); 2 * n - 1], } } #[inline] fn lazy_evaluate_node(&mut self, k: usize, height: usize) { if self.lazy[k] == R::upe() { return; } self.dat[k] = R::update(self.dat[k], self.lazy[k], height); if k < self.n - 1 { self.lazy[2 * k + 1] = R::upop(self.lazy[2 * k + 1], self.lazy[k]); self.lazy[2 * k + 2] = R::upop(self.lazy[2 * k + 2], self.lazy[k]); } self.lazy[k] = R::upe(); // identity for upop } #[inline] fn update_node(&mut self, k: usize) { self.dat[k] = R::biop(self.dat[2 * k + 1], self.dat[2 * k + 2]); } fn update_sub(&mut self, a: usize, b: usize, v: R::U, k: usize, height: usize, l: usize, r: usize) { self.lazy_evaluate_node(k, height); // [a,b) and [l,r) intersects? if r <= a || b <= l {return;} if a <= l && r <= b { self.lazy[k] = R::upop(self.lazy[k], v); self.lazy_evaluate_node(k, height); return; } self.update_sub(a, b, v, 2 * k + 1, height - 1, l, (l + r) / 2); self.update_sub(a, b, v, 2 * k + 2, height - 1, (l + r) / 2, r); self.update_node(k); } /* ary[i] = upop(ary[i], v) for i in [a, b) (half-inclusive) */ #[inline] pub fn update(&mut self, a: usize, b: usize, v: R::U) { let n = self.n; let dep = self.dep; self.update_sub(a, b, v, 0, dep, 0, n); } /* l,r are for simplicity */ fn query_sub(&mut self, a: usize, b: usize, k: usize, height: usize, l: usize, r: usize) -> R::T { self.lazy_evaluate_node(k, height); // [a,b) and [l,r) intersect? if r <= a || b <= l {return R::e();} if a <= l && r <= b {return self.dat[k];} let vl = self.query_sub(a, b, 2 * k + 1, height - 1, l, (l + r) / 2); let vr = self.query_sub(a, b, 2 * k + 2, height - 1, (l + r) / 2, r); self.update_node(k); R::biop(vl, vr) } /* [a, b) (note: half-inclusive) */ #[inline] pub fn query(&mut self, a: usize, b: usize) -> R::T { let n = self.n; let dep = self.dep; self.query_sub(a, b, 0, dep, 0, n) } } enum AddMin {} const INF: i64 = 1 << 50; impl ActionRing for AddMin { type T = i64; // data type U = i64; // action, a |-> x |-> a + x fn biop(x: Self::T, y: Self::T) -> Self::T { std::cmp::min(x, y) } fn update(x: Self::T, a: Self::U, _height: usize) -> Self::T { x + a } fn upop(fst: Self::U, snd: Self::U) -> Self::U { fst + snd } fn e() -> Self::T { INF } fn upe() -> Self::U { // identity for upop 0 } } // Tags: mos-algorithm fn main() { let out = std::io::stdout(); let mut out = BufWriter::new(out.lock()); macro_rules! puts {($($format:tt)*) => (let _ = write!(out,$($format)*););} input! { n: usize, q: usize, a: [usize1; n], lr: [(usize1, usize); q], } let mut lri = vec![(0, 0, 0); q]; for i in 0..q { let (l, r) = lr[i]; lri[i] = (l, r, i); } const B: usize = 300; lri.sort_by_key(|&(l, r, _)| { let q = l / B; (q, if q % 2 == 0 { r } else { n - r }) }); let mut ans = vec![0; q]; let mut x = 0; let mut y = n; let mut inv = 0i64; let mut side = LazySegTree::::with(&vec![0; n]); for &(l, r, idx) in &lri { while y < r { let v = a[y]; side.update(v + 1, n, -1); inv -= side.query(v, v + 1); y += 1; } while x > l { x -= 1; let v = a[x]; side.update(0, v, -1); inv -= side.query(v, v + 1); } while y > r { y -= 1; let v = a[y]; inv += side.query(v, v + 1); side.update(v + 1, n, 1); } while x < l { let v = a[x]; inv += side.query(v, v + 1); side.update(0, v, 1); x += 1; } ans[idx] = inv + side.query(0, n) * (r - l) as i64; } for i in 0..q { puts!("{}\n", ans[i]); } }