use std::ptr::NonNull; pub trait Cluster: Clone + std::fmt::Debug { type V: Default + Copy + std::fmt::Debug; fn identity() -> Self; fn compress(left: Self, right: Self, a: Self::V, b: Self::V, c: Self::V) -> Self; fn rake(left: Self, right: Self, a: Self::V, b: Self::V, c: Self::V) -> Self; fn reverse(&mut self); } pub type Link = Option; pub struct VertexRaw { val: T::V, handle: Option> } impl VertexRaw { pub fn new(val: T::V) -> Self { VertexRaw { val: val, handle: None, } } pub fn dummy() -> Self { VertexRaw { val: T::V::default(), handle: None, } } pub fn handle(&self) -> Option> { self.handle } pub fn handle_mut(&mut self) -> &mut Option> { &mut self.handle } pub fn value(&self) -> T::V { self.val } pub fn value_set(&mut self, val: T::V) { let mut root = expose_raw(self.handle().unwrap()); self.val = val; root.fix(); } } pub struct Vertex { vertex: NonNull>, } impl Vertex { pub fn dangling() -> Self { Vertex { vertex: NonNull::dangling() } } pub fn new(val: T::V) -> Self { unsafe { let v = Vertex { vertex: NonNull::new_unchecked(Box::into_raw(Box::new(VertexRaw::new(val)))) }; let dummy = Vertex { vertex: NonNull::new_unchecked(Box::into_raw(Box::new(VertexRaw::dummy()))) }; link(v, dummy, T::identity()); v } } pub fn handle(&self) -> Option> { unsafe { self.vertex.as_ref().handle() } } pub fn handle_mut(&mut self) -> &mut Option> { unsafe { self.vertex.as_mut().handle_mut() } } pub fn value(&self) -> T::V { unsafe { self.vertex.as_ref().value() } } pub fn value_set(&mut self, val: T::V) { unsafe { self.vertex.as_mut().value_set(val); } } } impl Clone for Vertex { fn clone(&self) -> Self { Vertex { vertex: self.vertex.clone() } } } impl Copy for Vertex {} impl PartialEq for Vertex { fn eq(&self, other: &Self) -> bool { self.vertex == other.vertex } } pub enum CompNode { Node(NonNull>), Leaf(NonNull>), } pub enum RakeNode { Node(NonNull>), Leaf(CompNode), } pub enum ParentNode { Compress(NonNull>), Rake(NonNull>), } pub struct Edge { v: [Vertex; 2], par: Link>, me: NonNull>, pub val: T, } pub struct Compress { ch: [CompNode; 2], v: [Vertex; 2], rake: Link>, par: Link>, me: NonNull>, rev: bool, pub guard: bool, pub fold: T } pub struct Rake { ch: [RakeNode; 2], v: [Vertex; 2], par: Link>, fold: T, } impl Edge { pub fn new(v: Vertex, u: Vertex, val: T) -> NonNull> { unsafe { let mut e = NonNull::new_unchecked(Box::into_raw(Box::new(Edge { v: [v, u], par: None, val: val, me: NonNull::dangling(), }))); e.as_mut().me = e; e.as_mut().fix(); e } } } impl Compress { pub fn new(left: CompNode, right: CompNode) -> NonNull> { unsafe { let mut n = NonNull::new_unchecked(Box::into_raw(Box::new(Compress { ch: [left, right], v: [Vertex::dangling(), Vertex::dangling()], rake: None, par: None, rev: false, me: NonNull::dangling(), guard: false, fold: T::identity(), }))); n.as_mut().me = n; n.as_mut().fix(); n } } } impl Rake { pub fn new(left: RakeNode, right: RakeNode) -> NonNull> { unsafe { let mut r = NonNull::new_unchecked(Box::into_raw(Box::new(Rake { ch: [left, right], v: [Vertex::dangling(), Vertex::dangling()], par: None, fold: T::identity() }))); r.as_mut().fix(); r } } } pub trait TVertex { fn fix(&mut self); fn push(&mut self); fn reverse(&mut self); fn parent(&self) -> Link>; fn parent_mut(&mut self) -> &mut Link>; } pub trait Node: TVertex { type Child: TVertex; fn child(&self, dir: usize) -> Self::Child; fn child_mut(&mut self, dir: usize) -> &mut Self::Child; } impl TVertex for Edge { fn fix(&mut self) { match self.parent() { Some(ParentNode::Compress(_)) => { if parent_dir_comp(CompNode::Leaf(self.me)).is_none() { *self.v[0].handle_mut() = Some(CompNode::Leaf(self.me)); } } Some(ParentNode::Rake(_)) => { *self.v[0].handle_mut() = Some(CompNode::Leaf(self.me)); } _ => { *self.v[0].handle_mut() = Some(CompNode::Leaf(self.me)); *self.v[1].handle_mut() = Some(CompNode::Leaf(self.me)); } } } fn push(&mut self) {} fn reverse(&mut self) { self.v.swap(0, 1); self.val.reverse(); } fn parent(&self) -> Link> { self.par } fn parent_mut(&mut self) -> &mut Link> { &mut self.par } } impl Compress { pub fn rake(&self) -> Link> { self.rake } pub fn rake_mut(&mut self) -> &mut Link> { &mut self.rake } } impl TVertex for Compress { fn fix(&mut self) { self.push(); self.v[0] = self.ch[0].endpoints(0); self.v[1] = self.ch[1].endpoints(1); //self.fold = self.ch[0].fold() + self.ch[1].fold(); self.fold = T::compress( match self.rake { Some(r) => T::rake(self.ch[0].fold(), r.fold(), self.ch[0].endpoints(0).value(), r.endpoints(0).value(), self.ch[0].endpoints(1).value()), None => self.ch[0].fold(), }, self.ch[1].fold(), self.ch[0].endpoints(0).value(), self.ch[1].endpoints(1).value(), self.ch[0].endpoints(1).value() ); *self.ch[0].endpoints(1).handle_mut() = Some(CompNode::Node(self.me)); /*println!("fix====="); for i in 0..2 { for j in 0..2 { println!("{}, {} = {}", i, j, self.ch[0].endpoints(i) == self.ch[1].endpoints(j)); } }*/ assert!(self.ch[0].endpoints(1) == self.ch[1].endpoints(0)); match self.parent() { Some(ParentNode::Compress(_)) => { if parent_dir_comp(CompNode::Node(self.me)).is_none() { *self.v[0].handle_mut() = Some(CompNode::Node(self.me)); } }, Some(ParentNode::Rake(_)) => { *self.v[0].handle_mut() = Some(CompNode::Node(self.me)); } _ => { *self.v[0].handle_mut() = Some(CompNode::Node(self.me)); *self.v[1].handle_mut() = Some(CompNode::Node(self.me)); } } } fn push(&mut self) { if self.rev { self.ch[0].reverse(); self.ch[1].reverse(); self.rev = false; } } fn reverse(&mut self) { self.ch.swap(0, 1); self.v.swap(0, 1); self.fold.reverse(); self.rev ^= true; self.push(); } fn parent(&self) -> Link> { self.par } fn parent_mut(&mut self) -> &mut Link> { &mut self.par } } impl Node for Compress { type Child = CompNode; fn child(&self, dir: usize) -> Self::Child { self.ch[dir] } fn child_mut(&mut self, dir: usize) -> &mut Self::Child { &mut self.ch[dir] } } impl TVertex for Rake { fn fix(&mut self) { self.push(); self.v = [self.ch[0].endpoints(0), self.ch[0].endpoints(1)]; self.fold = T::rake(self.ch[0].fold(), self.ch[1].fold(), self.ch[0].endpoints(0).value(), self.ch[1].endpoints(0).value(), self.ch[0].endpoints(1).value()); } fn push(&mut self) { } fn reverse(&mut self) { self.push(); } fn parent(&self) -> Link> { self.par } fn parent_mut(&mut self) -> &mut Link> { &mut self.par } } impl Node for Rake { type Child = RakeNode; fn child(&self, dir: usize) -> Self::Child { self.ch[dir] } fn child_mut(&mut self, dir: usize) -> &mut Self::Child { &mut self.ch[dir] } } impl CompNode { pub fn endpoints(&self, dir: usize) -> Vertex { unsafe { match *self { CompNode::Node(node) => node.as_ref().v[dir], CompNode::Leaf(leaf) => leaf.as_ref().v[dir], } } } pub fn fold(&self) -> T { unsafe { match *self { CompNode::Node(node) => node.as_ref().fold.clone(), CompNode::Leaf(leaf) => leaf.as_ref().val.clone(), } } } } impl RakeNode { pub fn endpoints(&self, dir: usize) -> Vertex { unsafe { match *self { RakeNode::Node(node) => node.as_ref().v[dir], RakeNode::Leaf(leaf) => leaf.endpoints(dir), } } } pub fn fold(&self) -> T { unsafe { match *self { RakeNode::Node(node) => node.as_ref().fold.clone(), RakeNode::Leaf(leaf) => leaf.fold(), } } } } impl TVertex for CompNode { fn fix(&mut self) { unsafe { match *self { CompNode::Node(mut node) => node.as_mut().fix(), CompNode::Leaf(mut leaf) => leaf.as_mut().fix(), } } } fn push(&mut self) { unsafe { match *self { CompNode::Node(mut node) => node.as_mut().push(), CompNode::Leaf(mut leaf) => leaf.as_mut().push(), } } } fn reverse(&mut self) { unsafe { match *self { CompNode::Node(mut node) => node.as_mut().reverse(), CompNode::Leaf(mut leaf) => leaf.as_mut().reverse(), } } } fn parent(&self) -> Link> { unsafe { match *self { CompNode::Node(node) => node.as_ref().parent(), CompNode::Leaf(leaf) => leaf.as_ref().parent(), } } } fn parent_mut(&mut self) -> &mut Link> { unsafe { match self { CompNode::Node(ref mut node) => node.as_mut().parent_mut(), CompNode::Leaf(ref mut leaf) => leaf.as_mut().parent_mut(), } } } } impl TVertex for RakeNode { fn fix(&mut self) { unsafe { match *self { RakeNode::Node(mut node) => node.as_mut().fix(), RakeNode::Leaf(mut leaf) => leaf.fix(), } } } fn push(&mut self) { unsafe { match *self { RakeNode::Node(mut node) => node.as_mut().push(), RakeNode::Leaf(mut leaf) => leaf.push(), } } } fn reverse(&mut self) { unsafe { match *self { RakeNode::Node(mut node) => node.as_mut().reverse(), RakeNode::Leaf(mut leaf) => leaf.reverse(), } } } fn parent(&self) -> Link> { unsafe { match *self { RakeNode::Node(node) => node.as_ref().parent(), RakeNode::Leaf(leaf) => leaf.parent(), } } } fn parent_mut(&mut self) -> &mut Link> { unsafe { match self { RakeNode::Node(ref mut node) => node.as_mut().parent_mut(), RakeNode::Leaf(ref mut leaf) => leaf.parent_mut(), } } } } impl TVertex for ParentNode { fn fix(&mut self) { unsafe { match *self { ParentNode::Compress(mut node) => node.as_mut().fix(), ParentNode::Rake(mut leaf) => leaf.as_mut().fix(), } } } fn push(&mut self) { unsafe { match *self { ParentNode::Compress(mut node) => node.as_mut().push(), ParentNode::Rake(mut leaf) => leaf.as_mut().push(), } } } fn reverse(&mut self) { unsafe { match *self { ParentNode::Compress(mut node) => node.as_mut().reverse(), ParentNode::Rake(mut leaf) => leaf.as_mut().reverse(), } } } fn parent(&self) -> Link> { unsafe { match *self { ParentNode::Compress(node) => node.as_ref().parent(), ParentNode::Rake(leaf) => leaf.as_ref().parent(), } } } fn parent_mut(&mut self) -> &mut Link> { unsafe { match self { ParentNode::Compress(ref mut node) => node.as_mut().parent_mut(), ParentNode::Rake(ref mut leaf) => leaf.as_mut().parent_mut(), } } } } impl PartialEq for CompNode { fn eq(&self, other: &Self) -> bool { match (*self, *other) { (CompNode::Node(a), CompNode::Node(b)) => a == b, (CompNode::Leaf(a), CompNode::Leaf(b)) => a == b, _ => false, } } } impl PartialEq for RakeNode { fn eq(&self, other: &Self) -> bool { match (*self, *other) { (RakeNode::Node(a), RakeNode::Node(b)) => a == b, (RakeNode::Leaf(a), RakeNode::Leaf(b)) => a == b, _ => false, } } } impl PartialEq for ParentNode { fn eq(&self, other: &Self) -> bool { match (*self, *other) { (ParentNode::Compress(a), ParentNode::Compress(b)) => a == b, (ParentNode::Rake(a), ParentNode::Rake(b)) => a == b, _ => false, } } } impl Clone for CompNode { fn clone(&self) -> Self { match *self { CompNode::Node(a) => CompNode::Node(a), CompNode::Leaf(a) => CompNode::Leaf(a), } } } impl Clone for RakeNode { fn clone(&self) -> Self { match *self { RakeNode::Node(a) => RakeNode::Node(a), RakeNode::Leaf(a) => RakeNode::Leaf(a), } } } impl Clone for ParentNode { fn clone(&self) -> Self { match *self { ParentNode::Compress(a) => ParentNode::Compress(a), ParentNode::Rake(a) => ParentNode::Rake(a), } } } impl Copy for CompNode {} impl Copy for RakeNode {} impl Copy for ParentNode {} pub fn parent_dir_comp(child: CompNode) -> Option<(usize, NonNull>)> { unsafe { match child.parent() { Some(ParentNode::Compress(mut p)) => { p.as_mut().push(); if p.as_ref().guard { None } else if p.as_ref().child(0) == child { Some((0, p)) } else if p.as_ref().child(1) == child { Some((1, p)) } else { None } } _ => None, } } } pub fn parent_dir_comp_guard(child: CompNode) -> Option<(usize, NonNull>)> { unsafe { match child.parent() { Some(ParentNode::Compress(mut p)) => { p.as_mut().push(); if p.as_ref().child(0) == child { Some((0, p)) } else if p.as_ref().child(1) == child { Some((1, p)) } else { None } } _ => None, } } } pub fn parent_dir_comp_rake(child: CompNode) -> Option<(usize, NonNull>)> { unsafe { match child.parent() { Some(ParentNode::Rake(mut p)) => { p.as_mut().push(); if p.as_ref().child(0) == RakeNode::Leaf(child) { Some((0, p)) } else if p.as_ref().child(1) == RakeNode::Leaf(child) { Some((1, p)) } else { None } } _ => None, } } } pub fn parent_dir_rake(child: RakeNode) -> Option<(usize, NonNull>)> { unsafe { match child.parent() { Some(ParentNode::Rake(mut p)) => { p.as_mut().push(); if p.as_ref().child(0) == child { Some((0, p)) } else if p.as_ref().child(1) == child { Some((1, p)) } else { None } } _ => None, } } } pub fn rotate_comp(mut t: NonNull>, mut x: NonNull>, dir: usize) { unsafe { let y = x.as_ref().parent(); if let Some(mut yy) = y { yy.push() } let par = parent_dir_comp_guard(CompNode::Node(x)); let rake_par = parent_dir_comp_rake(CompNode::Node(x)); *x.as_mut().child_mut(dir ^ 1) = t.as_ref().child(dir); *t.as_ref().child(dir).parent_mut() = Some(ParentNode::Compress(x)); *t.as_mut().child_mut(dir) = CompNode::Node(x); *x.as_mut().parent_mut() = Some(ParentNode::Compress(t)); x.as_mut().fix(); t.as_mut().fix(); *t.as_mut().parent_mut() = y; if let Some((xdir, mut yy)) = par { *yy.as_mut().child_mut(xdir) = CompNode::Node(t); //println!("yy==========================="); //test_comp_endpoints(CompNode::Node(yy)); if !yy.as_ref().guard { yy.as_mut().fix(); } } else if let Some((xdir, mut yy)) = rake_par { *yy.as_mut().child_mut(xdir) = RakeNode::Leaf(CompNode::Node(t)); yy.as_mut().fix(); } } } pub fn rotate_rake(mut t: NonNull>, mut x: NonNull>, dir: usize) { unsafe { let y = x.as_ref().parent(); if let Some(mut yy) = y { yy.push() } let par = parent_dir_rake(RakeNode::Node(x)); *x.as_mut().child_mut(dir ^ 1) = t.as_ref().child(dir); *t.as_ref().child(dir).parent_mut() = Some(ParentNode::Rake(x)); *t.as_mut().child_mut(dir) = RakeNode::Node(x); *x.as_mut().parent_mut() = Some(ParentNode::Rake(t)); x.as_mut().fix(); t.as_mut().fix(); *t.as_mut().parent_mut() = y; if let Some((xdir, mut yy)) = par { *yy.as_mut().child_mut(xdir) = RakeNode::Node(t); yy.as_mut().fix(); } else if let Some(ParentNode::Compress(mut yy)) = y { *yy.as_mut().rake_mut() = Some(RakeNode::Node(t)); //test_comp_print(CompNode::Node(yy)); //test_comp_print(yy.as_ref().child(0)); //test_comp_print(yy.as_ref().child(1)); if !yy.as_ref().guard { yy.as_mut().fix(); } } } } pub fn splay_comp(mut t: NonNull>) { unsafe { t.as_mut().push(); t.as_mut().fix(); while let Some((_,mut q)) = parent_dir_comp(CompNode::Node(t)) { q.as_mut().push(); if let Some((_, mut r)) = parent_dir_comp(CompNode::Node(q)) { r.as_mut().push(); q.as_mut().push(); t.as_mut().push(); let qt_dir = parent_dir_comp(CompNode::Node(t)).unwrap().0; let rq_dir = parent_dir_comp(CompNode::Node(q)).unwrap().0; if rq_dir == qt_dir { rotate_comp(q, r, rq_dir ^ 1); rotate_comp(t, q, qt_dir ^ 1); } else { rotate_comp(t, q, qt_dir ^ 1); rotate_comp(t, r, rq_dir ^ 1); } } else { let qt_dir = parent_dir_comp(CompNode::Node(t)).unwrap().0; t.as_mut().push(); //println!("t ====================="); //test_comp_print(CompNode::Node(t)); //println!("============="); //test_comp_endpoints(CompNode::Node(q)); rotate_comp(t, q, qt_dir ^ 1); } } } //println!("====================== end splay ================================="); } pub fn splay_rake(mut t: NonNull>) { unsafe { t.as_mut().push(); t.as_mut().fix(); while let Some((_, mut q)) = parent_dir_rake(RakeNode::Node(t)) { q.as_mut().push(); if let Some((_, mut r)) = parent_dir_rake(RakeNode::Node(q)) { r.as_mut().push(); q.as_mut().push(); t.as_mut().push(); let qt_dir = parent_dir_rake(RakeNode::Node(t)).unwrap().0; let rq_dir = parent_dir_rake(RakeNode::Node(q)).unwrap().0; if rq_dir == qt_dir { rotate_rake(q, r, rq_dir ^ 1); rotate_rake(t, q, qt_dir ^ 1); } else { rotate_rake(t, q, qt_dir ^ 1); rotate_rake(t, r, rq_dir ^ 1); } } else { let qt_dir = parent_dir_rake(RakeNode::Node(t)).unwrap().0; t.as_mut().push(); rotate_rake(t, q, qt_dir ^ 1); } } } } pub fn expose_raw(mut node: CompNode) -> CompNode { loop { //println!("function expose --- node"); //test_comp_print(node); //println!("endpoints ---------------------"); /*test_comp_endpoints( { let mut nn = node; while let Some((_dir, par)) = parent_dir_comp(nn) { nn = CompNode::Node(par); } nn } );*/ if let CompNode::Node(comp) = node { splay_comp(comp); } let mut n = match node.parent() { None => break, Some(ParentNode::Rake(mut par)) => { unsafe { par.as_mut().push(); } splay_rake(par); //unsafe { println!("{}", par.as_ref().parent().is_none()); } //unsafe { println!("{}", if let Some(ParentNode::Rake(_)) = par.as_ref().parent() { true } else { false }); } if let Some(ParentNode::Compress(n)) = unsafe { par.as_ref().parent() } { n } else { unreachable!() } } Some(ParentNode::Compress(mut n)) => { unsafe { n.as_mut().push(); } unsafe { if n.as_ref().guard && parent_dir_comp_guard(node).is_some() { break } } n } }; //println!("splay_comp_n ---------------------"); //test_comp_endpoints(CompNode::Node(n)); splay_comp(n); //println!("aaa====="); //test_comp_endpoints(CompNode::Node(n)); //println!("node"); //test_comp_print(node); let dir = match parent_dir_comp_guard(CompNode::Node(n)) { Some((dir, _)) => dir, None => 0, }; if dir == 1 { unsafe { n.as_ref().child(dir).reverse(); n.as_ref().child(dir).push(); node.reverse(); node.push(); } } if let Some((n_dir, mut rake)) = parent_dir_rake(RakeNode::Leaf(node)) { unsafe { let mut nch = n.as_mut().child(dir); *rake.as_mut().child_mut(n_dir) = RakeNode::Leaf(nch); *nch.parent_mut() = Some(ParentNode::Rake(rake)); *n.as_mut().child_mut(dir) = node; *node.parent_mut() = Some(ParentNode::Compress(n)); nch.fix(); rake.as_mut().fix(); node.fix(); n.as_mut().fix(); splay_rake(rake); //println!("=================2==================="); //test_comp_endpoints(CompNode::Node(n)); } } else { unsafe { let mut nch = n.as_mut().child(dir); *n.as_mut().rake_mut() = Some(RakeNode::Leaf(nch)); *nch.parent_mut() = Some(ParentNode::Compress(n)); *n.as_mut().child_mut(dir) = node; *node.parent_mut() = Some(ParentNode::Compress(n)); nch.fix(); node.fix(); //println!("=================1==================="); //test_comp_endpoints(CompNode::Node(n)); n.as_mut().fix(); } } if let CompNode::Leaf(_) = node { node = CompNode::Node(n); } } node } pub fn expose(ver: Vertex) -> CompNode { expose_raw(ver.handle().unwrap()) } pub fn soft_expose(v: Vertex, u: Vertex) { unsafe { let mut root = expose(v); if v.handle() == u.handle() { if root.endpoints(1) == v || root.endpoints(0) == u { root.reverse(); root.push(); } return; } if root.endpoints(0) == v { unreachable!(); root.reverse(); root.push(); } if root.endpoints(1) == v { unreachable!(); expose(u); } else if let CompNode::Node(mut r) = root { r.as_mut().guard = true; //println!("guard ---------------"); //test_comp_print(root); //test_comp_print(u.as_ref().1.unwrap()); let soot = expose(u); r.as_mut().guard = false; r.as_mut().fix(); if parent_dir_comp(soot).unwrap().0 == 0 { root.reverse(); root.push(); } } else { unreachable!() } } } pub fn link(v: Vertex, u: Vertex, weight: T) -> NonNull> { unsafe { if v.handle().is_none() && u.handle().is_none() { Edge::new(v, u, weight) } else { let nnu = u.handle(); let nnv = v.handle(); let mut e = Edge::new(v, u, weight); let mut left = match nnu { None => { CompNode::Leaf(e) } Some(uu) => { let mut uu = expose_raw(uu); uu.push(); if uu.endpoints(1) == u { uu.reverse(); uu.push(); } if uu.endpoints(0) == u { let mut nu = Compress::new(CompNode::Leaf(e), uu); *e.as_mut().parent_mut() = Some(ParentNode::Compress(nu)); e.as_mut().fix(); *uu.parent_mut() = Some(ParentNode::Compress(nu)); uu.fix(); nu.as_mut().fix(); CompNode::Node(nu) } else { let mut nu = match uu { CompNode::Node(nu) => nu, _ => unreachable!(), }; let mut left_ch = nu.as_ref().child(0); *nu.as_mut().child_mut(0) = CompNode::Leaf(e); *e.as_mut().parent_mut() = Some(ParentNode::Compress(nu)); e.as_mut().fix(); let beta = nu.as_ref().rake(); let mut rake = match beta { Some(mut b) => { let rake = Rake::new(b, RakeNode::Leaf(left_ch)); *b.parent_mut() = Some(ParentNode::Rake(rake)); *left_ch.parent_mut() = Some(ParentNode::Rake(rake)); left_ch.fix(); b.fix(); RakeNode::Node(rake) } None => { RakeNode::Leaf(left_ch) } }; rake.fix(); *nu.as_mut().rake_mut() = Some(rake); *rake.parent_mut() = Some(ParentNode::Compress(nu)); rake.fix(); nu.as_mut().fix(); CompNode::Node(nu) } } }; match nnv { None => {} Some(vv) => { let mut vv = expose_raw(vv); vv.push(); if vv.endpoints(0) == v { vv.reverse(); vv.push(); } if vv.endpoints(1) == v { let mut top = Compress::new(vv, left); *vv.parent_mut() = Some(ParentNode::Compress(top)); vv.fix(); *left.parent_mut() = Some(ParentNode::Compress(top)); left.fix(); top.as_mut().fix(); } else { let mut nv = match vv { CompNode::Node(nv) => nv, _ => unreachable!(), }; let mut right_ch = nv.as_ref().child(1); right_ch.reverse(); right_ch.push(); *nv.as_mut().child_mut(1) = left; *left.parent_mut() = Some(ParentNode::Compress(nv)); left.fix(); let alpha = nv.as_ref().rake(); let mut rake = match alpha { Some(mut a) => { let mut rake = Rake::new(a, RakeNode::Leaf(right_ch)); *a.parent_mut() = Some(ParentNode::Rake(rake)); a.fix(); *right_ch.parent_mut() = Some(ParentNode::Rake(rake)); right_ch.fix(); rake.as_mut().fix(); RakeNode::Node(rake) } None => { RakeNode::Leaf(right_ch) } }; rake.fix(); *nv.as_mut().rake_mut() = Some(rake); *rake.parent_mut() = Some(ParentNode::Compress(nv)); rake.fix(); //test_comp_print(nv.as_ref().child(0)); //test_comp_print(nv.as_ref().child(1)); //println!("-------------"); nv.as_mut().fix(); } } } e } } } fn bring(mut root: NonNull>) { unsafe { match root.as_ref().rake() { None => { let mut left = root.as_ref().child(0); let _ = Box::from_raw(root.as_ptr()); *left.parent_mut() = None; left.fix(); } Some(RakeNode::Leaf(mut new_right)) => { new_right.reverse(); new_right.push(); *root.as_mut().child_mut(1) = new_right; *new_right.parent_mut() = Some(ParentNode::Compress(root)); *root.as_mut().rake_mut() = None; new_right.fix(); root.as_mut().fix(); } Some(RakeNode::Node(mut rake)) => { rake.as_mut().push(); while let RakeNode::Node(mut right) = rake.as_ref().child(1) { right.as_mut().push(); rake = right; } root.as_mut().guard = true; splay_rake(rake); root.as_mut().guard = false; let mut new_rake = rake.as_ref().child(0); let mut new_right = if let RakeNode::Leaf(right) = rake.as_ref().child(1) { right } else { unreachable!() }; let _ = Box::from_raw(rake.as_ptr()); new_right.reverse(); new_right.push(); *root.as_mut().child_mut(1) = new_right; *new_right.parent_mut() = Some(ParentNode::Compress(root)); *root.as_mut().rake_mut() = Some(new_rake); *new_rake.parent_mut() = Some(ParentNode::Compress(root)); new_rake.fix(); new_right.fix(); root.as_mut().fix(); } } } } pub fn cut(v: Vertex, u: Vertex) { unsafe { soft_expose(v, u); let mut root = v.handle().unwrap(); root.push(); if let CompNode::Node(root) = root { let mut right = root.as_ref().child(1); *right.parent_mut() = None; right.reverse(); right.push(); if let CompNode::Node(right) = right { if let CompNode::Leaf(e) = right.as_ref().child(1) { bring(right); bring(root); let _ = Box::from_raw(e.as_ptr()); } else { unreachable!() } } else { unreachable!() } } else { unreachable!() } } } fn select_rake usize>(mut rake: RakeNode, sel: F, right: &mut (T, T::V, T::V)) -> CompNode { unsafe { rake.push(); while let RakeNode::Node(r) = rake { r.as_ref().child(0).push(); r.as_ref().child(0).fix(); r.as_ref().child(1).push(); r.as_ref().child(1).fix(); let (rf, r0, _r1) = (T::rake(r.as_ref().child(1).fold(), right.0.clone(), r.as_ref().child(1).endpoints(0).value(), right.1, r.as_ref().child(1).endpoints(1).value()), r.as_ref().child(1).endpoints(0).value(), r.as_ref().child(1).endpoints(1).value()); let dir = sel(r.as_ref().child(0).fold(), rf, r.as_ref().child(0).endpoints(0).value(), r0, r.as_ref().child(0).endpoints(1).value()); rake = r.as_ref().child(dir); *right = (T::rake(r.as_ref().child(1 - dir).fold(), right.0.clone(), r.as_ref().child(1 - dir).endpoints(0).value(), right.1, r.as_ref().child(1 - dir).endpoints(1).value()), r.as_ref().child(1 - dir).endpoints(0).value(), r.as_ref().child(1 - dir).endpoints(1).value()); rake.push(); } if let RakeNode::Leaf(comp) = rake { comp } else { unreachable!() } } } pub fn select usize>(v : Vertex, sel: F) -> (Vertex, Vertex) { let mut node = expose(v); let mut left = None; let mut right = None; unsafe { node.push(); while let CompNode::Node(n) = node { n.as_ref().child(0).push(); n.as_ref().child(0).fix(); n.as_ref().child(1).push(); n.as_ref().child(1).fix(); if let Some(mut r) = n.as_ref().rake() { r.push(); r.fix(); } let a = n.as_ref().child(0); let b = n.as_ref().child(1); let r = n.as_ref().rake(); let (af, a0, a1) = match left.clone() { Some((lf, l0, l1)) => (T::compress(lf, a.fold(), l0, a.endpoints(1).value(), l1), l0, a.endpoints(1).value()), None => (a.fold(), a.endpoints(0).value(), a.endpoints(1).value()), }; let (bf, b0, b1) = match right.clone() { Some((rf, _r0, r1)) => (T::compress(b.fold(), rf, b.endpoints(0).value(), r1, b.endpoints(1).value()), b.endpoints(0).value(), r1), None => (b.fold(), b.endpoints(0).value(), b.endpoints(1).value()), }; let dir = sel( match r { Some(r) => T::rake(af.clone(), r.fold(), a0, r.endpoints(0).value(), a1), None => af.clone(), }, bf.clone(), a0, b1, a1 ); node = if dir == 0 { if let Some(_) = r { let mut rbf = bf.clone(); rbf.reverse(); let rb0 = b1; let _rb1 = b0; let (mut rf, r0, r1) = (T::rake(r.unwrap().fold(), rbf.clone(), r.unwrap().endpoints(0).value(), rb0, r.unwrap().endpoints(1).value()), r.unwrap().endpoints(0).value(), r.unwrap().endpoints(1).value()); let dir = sel(af.clone(), rf.clone(), a0, r0, a1); if dir == 0 { rf.reverse(); right = Some((rf, r1, r0)); n.as_ref().child(0) } else { right = Some((T::rake(af, rbf, a0, rb0, a1), a0, a1)); let res = select_rake(n.as_ref().rake().unwrap(), &sel, right.as_mut().unwrap()); right = if let Some((mut rf, r0, r1)) = right.take() { rf.reverse(); Some((rf, r1, r0)) } else { None }; res } } else { right = Some((bf, b0, b1)); n.as_ref().child(0) } } else { left = match r { Some(r) => Some((T::rake(af.clone(), r.fold(), a0, r.endpoints(0).value(), a1), a0, a1)), None => Some((af, a0, a1)), }; n.as_ref().child(1) }; node.push(); } } if let CompNode::Leaf(_) = node { (node.endpoints(0), node.endpoints(1)) } else { unreachable!() } } pub fn test_comp_endpoints(node: CompNode) where T::V: Copy + std::fmt::Debug { unsafe { //node.push(); match node { CompNode::Node(n) => { println!("NODE {:?} = {:?}", [node.endpoints(0), node.endpoints(1)].iter().map(|v| v.value()).collect::>(), node.fold()); println!("left"); test_comp_endpoints(n.as_ref().child(0)); println!("right"); test_comp_endpoints(n.as_ref().child(1)); } CompNode::Leaf(_) => { println!("LEAF {:?} = {:?}", [node.endpoints(0), node.endpoints(1)].iter().map(|v| v.value()).collect::>(), node.fold()); } } } } pub fn test_comp_set(mut node: CompNode) where T::V: Copy + std::fmt::Debug { unsafe { node.push(); match node { CompNode::Node(n) => { println!("NODE {:?} = {:?}", [node.endpoints(0), node.endpoints(1)].iter().map(|v| v.value()).collect::>(), node.fold()); println!("left"); test_comp_print(n.as_ref().child(0)); println!("right"); test_comp_print(n.as_ref().child(1)); } CompNode::Leaf(_) => { println!("LEAF {:?} = {:?}", [node.endpoints(0), node.endpoints(1)].iter().map(|v| v.value()).collect::>(), node.fold()); } } } } pub fn test_comp_print(node: CompNode) where T::V: Copy + std::fmt::Debug { match node { CompNode::Node(_) => { println!("NODE {:?} = {:?}", [node.endpoints(0), node.endpoints(1)].iter().map(|v| v.value()).collect::>(), node.fold()); } CompNode::Leaf(_) => { println!("LEAF {:?} = {:?}", [node.endpoints(0), node.endpoints(1)].iter().map(|v| v.value()).collect::>(), node.fold()); } } } #[derive(Clone, Debug)] struct Median { inter_weight: usize, left_sum: usize, right_sum: usize, ans: usize, length: usize, } impl Median { fn new(l: usize) -> Self { Median { inter_weight: 0, ans: 0, left_sum: 0, right_sum: 0, length: l, } } } impl Cluster for Median { type V = usize; fn identity() -> Self { Median { inter_weight: 0, left_sum: 0, right_sum: 0, ans: 0, length: 0, } } fn compress(a: Self, b: Self, av: usize, bv: usize, cv: usize) -> Self { Median { inter_weight: a.inter_weight + b.inter_weight + cv, ans: a.right_sum + b.left_sum + a.length * av + b.length * bv, left_sum: a.left_sum + b.left_sum + a.length * (b.inter_weight + cv), right_sum: b.right_sum + a.right_sum + b.length * (a.inter_weight + cv), length: a.length + b.length, } } fn rake(a: Self, b: Self, _av: usize, bv: usize, _cv: usize) -> Self { Median { inter_weight: a.inter_weight + b.inter_weight + bv, ans: 0, left_sum: a.left_sum + b.right_sum + a.length * b.inter_weight + (a.length + b.length) * bv, right_sum: a.right_sum + b.right_sum + b.length * bv, length: a.length, } } fn reverse(&mut self) { std::mem::swap(&mut self.left_sum, &mut self.right_sum); } } use std::io::Read; fn main() { let mut buf = String::new(); std::io::stdin().read_to_string(&mut buf).unwrap(); let mut iter = buf.split_whitespace(); let n: usize = iter.next().unwrap().parse().unwrap(); let q: usize = iter.next().unwrap().parse().unwrap(); let mut v: Vec<_> = (0..n).map(|_| Vertex::new(1)).collect(); let mut sum = 0; for _ in 0..q { let query: usize = iter.next().unwrap().parse().unwrap(); if query == 1 { let a: usize = iter.next().unwrap().parse().unwrap(); let b: usize = iter.next().unwrap().parse().unwrap(); let c: usize = iter.next().unwrap().parse().unwrap(); let (a, b) = ((a - 1 + sum) % n, (b - 1 + sum) % n); //println!("link {} {}", a, b); link(v[a], v[b], Median::new(c)); } else if query == 2 { let a: usize = iter.next().unwrap().parse().unwrap(); let b: usize = iter.next().unwrap().parse().unwrap(); let (a, b) = ((a - 1 + sum) % n, (b - 1 + sum) % n); //println!("cut {} {}", a, b); cut(v[a], v[b]); } else if query == 3 { let a: usize = iter.next().unwrap().parse().unwrap(); let a = (a - 1 + sum) % n; let val = v[a].value(); v[a].value_set(1 - val); let (x, y) = select(v[a], |a, b, av, bv, cv| { if a.inter_weight + av + cv >= b.inter_weight + bv + cv { 0 } else { 1 } }); //println!("query 3 = {}", a); let ans = std::cmp::min(expose(x).fold().ans, expose(y).fold().ans); let ans = (0..n).filter(|i| { let root = expose(v[a]); expose(v[*i]); root.parent().is_some() || *i == a }).map(|i| expose(v[i]).fold().ans).min().unwrap(); sum = (sum + ans % n) % n; println!("{}", ans); } } }