結果
| 問題 | No.772 Dynamic Distance Sum |
| ユーザー |
 niuez
|
| 提出日時 | 2019-07-08 09:53:33 |
| 言語 | Rust (1.77.0 + proconio) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 41,866 bytes |
| コンパイル時間 | 14,344 ms |
| コンパイル使用メモリ | 379,744 KB |
| 実行使用メモリ | 47,008 KB |
| 最終ジャッジ日時 | 2024-10-07 22:14:32 |
| 合計ジャッジ時間 | 23,915 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
6,816 KB |
| testcase_01 | AC | 1 ms
6,820 KB |
| testcase_02 | AC | 1 ms
6,820 KB |
| testcase_03 | AC | 1 ms
6,816 KB |
| testcase_04 | RE | - |
| testcase_05 | RE | - |
| testcase_06 | RE | - |
| testcase_07 | RE | - |
| testcase_08 | RE | - |
| testcase_09 | RE | - |
| testcase_10 | RE | - |
| testcase_11 | RE | - |
| testcase_12 | RE | - |
| testcase_13 | RE | - |
| testcase_14 | RE | - |
| testcase_15 | RE | - |
| testcase_16 | RE | - |
| testcase_17 | RE | - |
| testcase_18 | RE | - |
| testcase_19 | RE | - |
| testcase_20 | RE | - |
| testcase_21 | RE | - |
| testcase_22 | RE | - |
| testcase_23 | TLE | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
ソースコード
use std::ptr::NonNull;
pub trait Cluster: Clone {
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<N> = Option<N>;
pub struct VertexRaw<T: Cluster> {
val: T::V,
handle: Option<CompNode<T>>
}
impl<T: Cluster> VertexRaw<T> {
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<CompNode<T>> {
self.handle
}
pub fn handle_mut(&mut self) -> &mut Option<CompNode<T>> {
&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<T: Cluster> {
vertex: NonNull<VertexRaw<T>>,
}
impl<T: Cluster> Vertex<T> {
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<CompNode<T>> {
unsafe { self.vertex.as_ref().handle() }
}
pub fn handle_mut(&mut self) -> &mut Option<CompNode<T>> {
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<T: Cluster> Clone for Vertex<T> {
fn clone(&self) -> Self {
Vertex { vertex: self.vertex.clone() }
}
}
impl<T: Cluster> Copy for Vertex<T> {}
impl<T: Cluster> PartialEq for Vertex<T> {
fn eq(&self, other: &Self) -> bool {
self.vertex == other.vertex
}
}
pub enum CompNode<T: Cluster> {
Node(NonNull<Compress<T>>),
Leaf(NonNull<Edge<T>>),
}
pub enum RakeNode<T: Cluster> {
Node(NonNull<Rake<T>>),
Leaf(CompNode<T>),
}
pub enum ParentNode<T: Cluster> {
Compress(NonNull<Compress<T>>),
Rake(NonNull<Rake<T>>),
}
pub struct Edge<T: Cluster> {
v: [Vertex<T>; 2],
par: Link<ParentNode<T>>,
me: NonNull<Edge<T>>,
pub val: T,
}
pub struct Compress<T: Cluster> {
ch: [CompNode<T>; 2],
v: [Vertex<T>; 2],
rake: Link<RakeNode<T>>,
par: Link<ParentNode<T>>,
me: NonNull<Compress<T>>,
rev: bool,
pub guard: bool,
pub fold: T
}
pub struct Rake<T: Cluster> {
ch: [RakeNode<T>; 2],
v: [Vertex<T>; 2],
par: Link<ParentNode<T>>,
fold: T,
}
impl<T: Cluster> Edge<T> {
pub fn new(v: Vertex<T>, u: Vertex<T>, val: T) -> NonNull<Edge<T>> {
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<T: Cluster> Compress<T> {
pub fn new(left: CompNode<T>, right: CompNode<T>) -> NonNull<Compress<T>> {
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<T: Cluster> Rake<T> {
pub fn new(left: RakeNode<T>, right: RakeNode<T>) -> NonNull<Rake<T>> {
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<T: Cluster> {
fn fix(&mut self);
fn push(&mut self);
fn reverse(&mut self);
fn parent(&self) -> Link<ParentNode<T>>;
fn parent_mut(&mut self) -> &mut Link<ParentNode<T>>;
}
pub trait Node<T: Cluster>: TVertex<T> {
type Child: TVertex<T>;
fn child(&self, dir: usize) -> Self::Child;
fn child_mut(&mut self, dir: usize) -> &mut Self::Child;
}
impl<T: Cluster> TVertex<T> for Edge<T> {
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<ParentNode<T>> { self.par }
fn parent_mut(&mut self) -> &mut Link<ParentNode<T>> { &mut self.par }
}
impl<T: Cluster> Compress<T> {
pub fn rake(&self) -> Link<RakeNode<T>> { self.rake }
pub fn rake_mut(&mut self) -> &mut Link<RakeNode<T>> { &mut self.rake }
}
impl<T: Cluster> TVertex<T> for Compress<T> {
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));
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<ParentNode<T>> { self.par }
fn parent_mut(&mut self) -> &mut Link<ParentNode<T>> { &mut self.par }
}
impl<T: Cluster> Node<T> for Compress<T> {
type Child = CompNode<T>;
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<T: Cluster> TVertex<T> for Rake<T> {
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<ParentNode<T>> { self.par }
fn parent_mut(&mut self) -> &mut Link<ParentNode<T>> { &mut self.par }
}
impl<T: Cluster> Node<T> for Rake<T> {
type Child = RakeNode<T>;
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<T: Cluster> CompNode<T> {
pub fn endpoints(&self, dir: usize) -> Vertex<T> {
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<T: Cluster> RakeNode<T> {
pub fn endpoints(&self, dir: usize) -> Vertex<T> {
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<T: Cluster> TVertex<T> for CompNode<T> {
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<ParentNode<T>> {
unsafe {
match *self {
CompNode::Node(node) => node.as_ref().parent(),
CompNode::Leaf(leaf) => leaf.as_ref().parent(),
}
}
}
fn parent_mut(&mut self) -> &mut Link<ParentNode<T>> {
unsafe {
match self {
CompNode::Node(ref mut node) => node.as_mut().parent_mut(),
CompNode::Leaf(ref mut leaf) => leaf.as_mut().parent_mut(),
}
}
}
}
impl<T: Cluster> TVertex<T> for RakeNode<T> {
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<ParentNode<T>> {
unsafe {
match *self {
RakeNode::Node(node) => node.as_ref().parent(),
RakeNode::Leaf(leaf) => leaf.parent(),
}
}
}
fn parent_mut(&mut self) -> &mut Link<ParentNode<T>> {
unsafe {
match self {
RakeNode::Node(ref mut node) => node.as_mut().parent_mut(),
RakeNode::Leaf(ref mut leaf) => leaf.parent_mut(),
}
}
}
}
impl<T: Cluster> TVertex<T> for ParentNode<T> {
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<ParentNode<T>> {
unsafe {
match *self {
ParentNode::Compress(node) => node.as_ref().parent(),
ParentNode::Rake(leaf) => leaf.as_ref().parent(),
}
}
}
fn parent_mut(&mut self) -> &mut Link<ParentNode<T>> {
unsafe {
match self {
ParentNode::Compress(ref mut node) => node.as_mut().parent_mut(),
ParentNode::Rake(ref mut leaf) => leaf.as_mut().parent_mut(),
}
}
}
}
impl<T: Cluster> PartialEq for CompNode<T> {
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<T: Cluster> PartialEq for RakeNode<T> {
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<T: Cluster> PartialEq for ParentNode<T> {
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<T: Cluster> Clone for CompNode<T> {
fn clone(&self) -> Self {
match *self {
CompNode::Node(a) => CompNode::Node(a),
CompNode::Leaf(a) => CompNode::Leaf(a),
}
}
}
impl<T: Cluster> Clone for RakeNode<T> {
fn clone(&self) -> Self {
match *self {
RakeNode::Node(a) => RakeNode::Node(a),
RakeNode::Leaf(a) => RakeNode::Leaf(a),
}
}
}
impl<T: Cluster> Clone for ParentNode<T> {
fn clone(&self) -> Self {
match *self {
ParentNode::Compress(a) => ParentNode::Compress(a),
ParentNode::Rake(a) => ParentNode::Rake(a),
}
}
}
impl<T: Cluster> Copy for CompNode<T> {}
impl<T: Cluster> Copy for RakeNode<T> {}
impl<T: Cluster> Copy for ParentNode<T> {}
pub fn parent_dir_comp<T: Cluster>(child: CompNode<T>) -> Option<(usize, NonNull<Compress<T>>)> {
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<T: Cluster>(child: CompNode<T>) -> Option<(usize, NonNull<Compress<T>>)> {
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<T: Cluster>(child: CompNode<T>) -> Option<(usize, NonNull<Rake<T>>)> {
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<T: Cluster>(child: RakeNode<T>) -> Option<(usize, NonNull<Rake<T>>)> {
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<T: Cluster>(mut t: NonNull<Compress<T>>, mut x: NonNull<Compress<T>>, 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));
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<T: Cluster>(mut t: NonNull<Rake<T>>, mut x: NonNull<Rake<T>>, 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));
yy.as_mut().fix();
}
}
}
pub fn splay_comp<T: Cluster>(mut t: NonNull<Compress<T>>) {
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<T: Cluster>(mut t: NonNull<Rake<T>>) {
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<T: Cluster>(mut node: CompNode<T>) -> CompNode<T> {
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();
node.reverse();
}
}
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();
splay_rake(rake);
//println!("=================2===================");
//test_comp_endpoints(CompNode::Node(n));
n.as_mut().fix();
}
}
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<T: Cluster>(ver: Vertex<T>) -> CompNode<T> {
expose_raw(ver.handle().unwrap())
}
pub fn soft_expose<T: Cluster>(v: Vertex<T>, u: Vertex<T>) {
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 {
root.reverse();
root.push();
}
if root.endpoints(1) == v {
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();
}
}
else {
unreachable!()
}
}
}
pub fn link<T: Cluster>(v: Vertex<T>, u: Vertex<T>, weight: T) -> NonNull<Edge<T>> {
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);
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();
RakeNode::Node(rake)
}
None => {
RakeNode::Leaf(left_ch)
}
};
*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);
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)
}
};
*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<T: Cluster>(mut root: NonNull<Compress<T>>) {
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;
}
splay_rake(rake);
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<T: Cluster>(v: Vertex<T>, u: Vertex<T>) {
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<T: Cluster, F: Fn(T, T, T::V, T::V, T::V) -> usize>(mut rake: RakeNode<T>, sel: F, right: &mut (T, T::V, T::V)) -> CompNode<T> {
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<T: Cluster, F: Fn(T, T, T::V, T::V, T::V) -> usize>(v : Vertex<T>, sel: F) -> (Vertex<T>, Vertex<T>) {
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, rf.clone(), a0, r0, a1);
if dir == 0 {
rf.reverse();
right = Some((rf, r1, r0));
n.as_ref().child(0)
}
else {
right = match left.take() {
Some((lf, l0, l1)) => {
Some((T::rake(lf, rbf, l0, rb0, l1), l0, l1))
}
None => Some((rbf, rb0, rb1)),
};
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 = Some((af, a0, a1));
n.as_ref().child(1)
};
node.push();
}
}
if let CompNode::Leaf(_) = node {
soft_expose(node.endpoints(0), node.endpoints(1));
(node.endpoints(0), node.endpoints(1))
}
else { unreachable!() }
}
#[derive(Clone)]
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);
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);
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 }
});
let ans = std::cmp::min(expose(x).fold().ans, expose(y).fold().ans);
sum = (sum + ans % n) % n;
println!("{}", ans);
}
}
}