#[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") }; } #[test] fn input_test() { input! { source = "2 4\n10 20 30 40", n: usize, m: usize, a: [usize; m], } assert_eq!(n, 2); assert_eq!(m, 4); assert_eq!(a, [10, 20, 30, 40]); } pub trait Magma: Sized + Clone { fn op(&self, rhs: &Self) -> Self; } pub trait Associative: Magma {} pub trait Unital: Magma { fn identity() -> Self; } pub trait Monoid: Magma + Associative + Unital {} pub trait Pow: Magma { fn pow(&self, p: usize) -> Self; } pub trait Reverse: Magma { fn reverse(&self) -> Self; } pub trait Inv: Magma { fn inv(&self) -> Self; } pub trait Effect { fn effect(&self, e: &E) -> Self; } impl Monoid for T {} #[macro_export] macro_rules! build_node_struct { ($node:ident, $val_type:ty, $($elem:ident: $t:ty,)*) => { struct $node { val: $val_type, child: [Link<$node>; 2], $($elem: $t),* } } } #[macro_export] macro_rules! define_node { ($node:ident, $val_type:ty | $($e:ident : $t:ty,)* | ) => { build_node_struct! { $node, $val_type, $($e: $t,)* } }; ($node:ident, $val_type:ty | $($e:ident : $t:ty,)* | size, $($elem:tt)*) => { define_node! { $node, $val_type | $($e: $t,)* size: usize, | $($elem)* } }; ($node:ident, $val_type:ty | $($e:ident : $t:ty,)* | fold, $($elem:tt)*) => { define_node! { $node, $val_type | $($e: $t,)* fold: $val_type, | $($elem)* } }; ($node:ident, $val_type:ty | $($e:ident : $t:ty,)* | rev, $($elem:tt)*) => { define_node! { $node, $val_type | $($e: $t,)* rev: bool, | $($elem)* } }; } #[macro_export] macro_rules! impl_node_new { ($node:ident, $val_type:ty, $($e:ident : $v: expr,)*) => { impl $node { fn new(val: $val_type) -> Self { Self { val: val, child: [None, None], $($e: $v),* } } } } } #[macro_export] macro_rules! impl_node_elem { ($node:ident, $val_type:ty | $($e:ident : $v:expr,)* | ) => { impl_node_new! { $node, $val_type, $($e: $v,)* } }; ($node:ident, $val_type:ty | $($e:ident : $v:expr,)* | size, $($elem:tt)*) => { impl_node_elem! { $node, $val_type | $($e: $v,)* size: 1, | $($elem)* } }; ($node:ident, $val_type:ty | $($e:ident : $v:expr,)* | fold, $($elem:tt)*) => { impl_node_elem! { $node, $val_type | $($e: $v,)* fold: <$val_type as Unital>::identity(), | $($elem)* } }; ($node:ident, $val_type:ty | $($e:ident : $v:expr,)* | rev, $($elem:tt)*) => { impl_node_elem! { $node, $val_type | $($e: $v,)* rev: false, | $($elem)* } }; } #[macro_export] macro_rules! impl_node_trait { ($node:ident, $val_type:ty, $($elem:tt)* ) => { impl Node for $node { type Value = $val_type; fn push(&mut self) { impl_push! { self, $val_type, $($elem)* } } fn fix(&mut self) { impl_fix! { self, $val_type, $($elem)* } } fn child(&self, dir: usize) -> &Link { &self.child[dir] } fn child_mut(&mut self, dir: usize) -> &mut Link { &mut self.child[dir] } fn take(&mut self, dir: usize) -> Link { let nn = self.child[dir].take(); self.fix(); nn } fn set(&mut self, dir: usize, node: Link ) { self.child[dir] = node; self.fix(); } fn value(&self) -> &Self::Value { &self.val } fn value_mut(&mut self) -> &mut Self::Value { &mut self.val } } } } #[macro_export] macro_rules! impl_push { ($mself:expr, $val_type:ty, ) => {}; ($mself:expr, $val_type:ty, rev, $($elem:tt)*) => { if $mself.rev { $mself.child.swap(0, 1); } $mself.rev = false; impl_push! { $mself, $val_type, $($elem)* } }; ($mself:expr, $val_type:ty, $head:tt, $($elem:tt)*) => { impl_push! { $mself, $val_type, $($elem)* } }; } #[macro_export] macro_rules! impl_fix { ($mself:expr, $val_type:ty, ) => {}; ($mself:expr, $val_type:ty, size, $($elem:tt)*) => { $mself.size = size(&$mself.child[0]) + size(&$mself.child[1]) + 1; impl_fix! { $mself, $val_type, $($elem)* } }; ($mself:expr, $val_type:ty, fold, $($elem:tt)*) => { $mself.fold = fold(&$mself.child[0]).op(&$mself.val).op(&fold(&$mself.child[1])); impl_fix! { $mself, $val_type, $($elem)* } }; ($mself:expr, $val_type:ty, $head:tt, $($elem:tt)*) => { impl_fix! { $mself, $val_type, $($elem)* } }; } #[macro_export] macro_rules! impl_rev_trait { ($node:ident, $val_type:ty, ) => {}; ($node:ident, $val_type:ty, rev, $($tail:tt)*) => { impl ReversibleNode for $node { fn reverse(&mut self) { self.rev ^= true; } } }; ($node:ident, $val_type:ty, $head:tt, $($elem:tt)*) => { impl_rev_trait! { $node, $val_type, $($elem)* } }; } #[macro_export] macro_rules! impl_rev2_trait { ($node:ident, $val_type:ty | off | off | ) => {}; ($node:ident, $val_type:ty | off | on | ) => {}; ($node:ident, $val_type:ty | on | off | ) => { impl ReversibleNode for $node { fn reverse(&mut self) { self.rev ^= true; } } }; ($node:ident, $val_type:ty | on | on | ) => { impl ReversibleNode for $node { fn reverse(&mut self) { self.rev ^= true; self.fold = self.fold.reverse(); } } }; ($node:ident, $val_type:ty | $r:tt | $f:tt | rev, $($tail:tt)*) => { impl_rev2_trait! { $node, $val_type | on | $f | $($tail)* } }; ($node:ident, $val_type:ty | $r:tt | $f:tt | fold, $($tail:tt)*) => { impl_rev2_trait! { $node, $val_type | $r | on | $($tail)* } }; ($node:ident, $val_type:ty | $r:tt | $f:tt | $head:tt, $($tail:tt)*) => { impl_rev2_trait! { $node, $val_type | $r | $f | $($tail)* } }; } #[macro_export] macro_rules! impl_size_trait { ($node:ident, $val_type:ty, ) => {}; ($node:ident, $val_type:ty, size, $($tail:tt)*) => { impl SizeNode for $node { fn size(&self) -> usize { self.size } } }; ($node:ident, $val_type:ty, $head:tt, $($elem:tt)*) => { impl_size_trait! { $node, $val_type, $($elem)* } }; } #[macro_export] macro_rules! impl_fold_trait { ($node:ident, $val_type:ty, ) => {}; ($node:ident, $val_type:ty, fold, $($tail:tt)*) => { impl FoldNode for $node { fn fold(&self) -> $val_type { self.fold.clone() } } }; ($node:ident, $val_type:ty, $head:tt, $($elem:tt)*) => { impl_fold_trait! { $node, $val_type, $($elem)* } }; } #[macro_export] macro_rules! def_node { ($node:ident, $val_type:ty; $($elem:tt)* ) => { define_node! { $node, $val_type | | $($elem)* } impl_node_elem! { $node, $val_type | | $($elem)* } impl_node_trait! { $node, $val_type, $($elem)* } impl_rev2_trait! { $node, $val_type | off | off | $($elem)* } impl_size_trait! { $node, $val_type, $($elem)* } impl_fold_trait! { $node, $val_type, $($elem)* } }; } pub type Link = Option>; pub trait Node: Sized { type Value; fn push(&mut self); fn fix(&mut self); fn child(&self, dir: usize) -> &Link; fn child_mut(&mut self, dir: usize) -> &mut Link; fn take(&mut self, dir: usize) -> Link; fn set(&mut self, dir: usize, node: Link); fn value(&self) -> &Self::Value; fn value_mut(&mut self) -> &mut Self::Value; } pub trait ReversibleNode: Node { fn reverse(&mut self); } pub trait SizeNode: Node { fn size(&self) -> usize; } pub trait FoldNode where Self: Node, ::Value: Monoid { fn fold(&self) -> ::Value; } pub fn size(link: &Link) -> usize { match *link { Some(ref node) => node.size(), None => 0, } } pub fn fold(link: &Link) -> ::Value where ::Value: Monoid { match *link { Some(ref node) => node.fold(), None => ::Value::identity(), } } use std::cmp::Ordering::{ Equal, Greater, Less }; pub trait SplayArrayNode: Node + SizeNode {} impl SplayArrayNode for N {} fn depth_fix(n: &mut Link, dir: usize) { if let Some(ref mut x) = n { depth_fix(x.as_mut().child_mut(dir), dir); x.as_mut().fix(); } } fn splay(mut root: Box, mut i: usize) -> Box { let mut top_left: Link = None; let mut top_right: Link = None; { let mut left = &mut top_left; let mut right = &mut top_right; loop { let ([le, ri], rt) = { let mut x = root; x.as_mut().push(); let alpha = match i.cmp(&size(x.child(0))) { Equal => { root = x; break } Less => { 0 } Greater => { i = i - size(x.child(0)) - 1; 1 } }; let mut y = x.as_mut().take(alpha).unwrap(); y.as_mut().push(); match i.cmp(&size(y.child(0))) { Equal => { if alpha == 0 { ([None, Some(x)], y) } else { ([Some(x), None], y) } } cm => { let beta = if cm == Less { 0 } else { i = i - size(y.child(0)) - 1; 1 }; let z = y.as_mut().take(beta).unwrap(); let mut res = [None, None]; if alpha == beta { x.as_mut().set(alpha, y.as_mut().take(alpha ^ 1)); y.as_mut().set(alpha ^ 1, Some(x)); res[alpha ^ 1] = Some(y); } else { res[alpha ^ 1] = Some(x); res[beta ^ 1] = Some(y); } (res, z) } } }; root = rt; if let Some(l) = le { *left = Some(l); let t = left; left = t.as_mut().unwrap().as_mut().child_mut(1); } if let Some(r) = ri { *right = Some(r); let t = right; right = t.as_mut().unwrap().as_mut().child_mut(0); } } std::mem::swap(&mut root.as_mut().take(0), left); std::mem::swap(&mut root.as_mut().take(1), right); } depth_fix(&mut top_left, 1); depth_fix(&mut top_right, 0); root.as_mut().set(0, top_left); root.as_mut().set(1, top_right); root } fn merge(x: Link, y: Link) -> Link { match x { Some(x) => { let sz = x.size(); let mut x = splay(x, sz - 1); x.as_mut().set(1, y); Some(x) } None => y } } fn split(x: Link, i: usize) -> (Link, Link) { assert!(i <= size(&x), "not validate spliting"); if i == 0 { (None, x) } else if i == size(&x) { (x, None) } else { let mut x = splay(x.unwrap(), i); let y = x.as_mut().take(0); (y, Some(x)) } } pub struct SplayArray { root: Link, } impl SplayArray { pub fn empty() -> Self { SplayArray { root: None } } pub fn new(node: N) -> Self { SplayArray { root: Some(Box::new(node)) } } pub fn len(&self) -> usize { size(&self.root) } pub fn merge(self, other: Self) -> Self { SplayArray { root: merge(self.root, other.root) } } pub fn split(self, i: usize) -> (Self, Self) { let (l, r) = split(self.root, i); ( SplayArray { root: l }, SplayArray { root: r }) } pub fn at(&mut self, i: usize) -> &N::Value { self.root = Some(splay(self.root.take().unwrap(), i)); self.root.as_ref().unwrap().value() } pub fn at_set(&mut self, i: usize, val: N::Value) { self.root = Some(splay(self.root.take().unwrap(), i)); *self.root.as_mut().unwrap().value_mut() = val; self.root.as_mut().unwrap().fix(); } pub fn take(&mut self) -> Self { SplayArray { root: self.root.take() } } pub fn range<'a>(&'a mut self, ran: std::ops::Range) -> SplayRange<'a, N> { let (l, r) = self.take().split(ran.end); let (l, c) = l.split(ran.start); SplayRange { before: self, left: l, center: c, right: r, } } } impl SplayArray where N::Value: Monoid { pub fn fold(&self) -> N::Value { fold(&self.root) } } impl SplayArray { pub fn reverse(&mut self) { self.root.as_mut().map(|r| r.as_mut().reverse()); } } pub struct SplayRange<'a, N: SplayArrayNode> { before: &'a mut SplayArray, left: SplayArray, center: SplayArray, right: SplayArray, } impl<'a, N: SplayArrayNode> Drop for SplayRange<'a, N> { fn drop(&mut self) { self.before.root = self.left.take() .merge(self.center.take()) .merge(self.right.take()) .root.take(); } } impl<'a, N: SplayArrayNode> SplayRange<'a, N> { pub fn take(&mut self) -> SplayArray { SplayArray { root: self.center.root.take() } } pub fn len(&self) -> usize { size(&self.center.root) } pub fn at(&mut self, i: usize) -> &N::Value { self.center.root = Some(splay(self.center.root.take().unwrap(), i)); self.center.root.as_ref().unwrap().value() } } impl<'a, N: SplayArrayNode + FoldNode> SplayRange<'a, N> where N::Value: Monoid { pub fn fold(&self) -> N::Value { fold(&self.center.root) } } impl<'a, N: SplayArrayNode + ReversibleNode> SplayRange<'a, N> { pub fn reverse(&mut self) { self.center.root.as_mut().map(|r| r.as_mut().reverse()); } } #[derive(Clone)] struct Mi(usize, usize); impl Magma for Mi { fn op(&self, rhs: &Self) -> Self { if self.0 < rhs.0 { self.clone() } else { rhs.clone() } } } impl Unital for Mi { fn identity() -> Self { Mi(202020, 0) } } impl Associative for Mi {} def_node! { No, Mi; size, fold, } fn main() { input! { n: usize, q: usize, a: [usize; n], query: [(usize, usize, usize); q], } let mut b = a; let mut sp = SplayArray::empty(); for i in 0..n { sp = sp.merge( SplayArray::new(No::new(Mi(b[i], i + 1))) ) } for (ty, l, r) in query { if ty == 1 { sp.at_set(l - 1, Mi(b[r - 1], l)); sp.at_set(r - 1, Mi(b[l - 1], r)); b.swap(l - 1, r - 1); } else { println!("{}", sp.range((l - 1)..r).fold().1); } } }