#388514 (Rust) No.875 Range Mindex Query

提出ソース
結果

問題	No.875 Range Mindex Query
ユーザー	niuez
提出日時	2019-10-11 09:58:49
言語	Rust (1.77.0 + proconio)
結果	AC
実行時間	463 ms / 2,000 ms
コード長	16,455 bytes
コンパイル時間	16,446 ms
コンパイル使用メモリ	378,632 KB
実行使用メモリ	13,568 KB
最終ジャッジ日時	2024-11-24 03:37:39
合計ジャッジ時間	17,308 ms
ジャッジサーバーID （参考情報）	judge2 / judge4
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 5,248 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	AC	3 ms 5,248 KB
testcase_03	AC	1 ms 5,248 KB
testcase_04	AC	2 ms 5,248 KB
testcase_05	AC	1 ms 5,248 KB
testcase_06	AC	2 ms 5,248 KB
testcase_07	AC	3 ms 5,248 KB
testcase_08	AC	2 ms 5,248 KB
testcase_09	AC	2 ms 5,248 KB
testcase_10	AC	3 ms 5,248 KB
testcase_11	AC	322 ms 11,776 KB
testcase_12	AC	260 ms 9,728 KB
testcase_13	AC	228 ms 11,648 KB
testcase_14	AC	217 ms 11,264 KB
testcase_15	AC	320 ms 13,056 KB
testcase_16	AC	430 ms 12,800 KB
testcase_17	AC	463 ms 13,312 KB
testcase_18	AC	454 ms 13,568 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#[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::<Vec<_>>()
    };
    
    // string
    ($iter:expr, chars) => {
        read_value!($iter, String).chars(),collect::<Vec<char>>()
    };
    
    // 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<E: Monoid> {
    fn effect(&self, e: &E) -> Self;
}

impl<T: Magma + Associative + Unital> 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> { &self.child[dir] } 
            fn child_mut(&mut self, dir: usize) -> &mut Link<Self> { &mut self.child[dir] } 
            fn take(&mut self, dir: usize) -> Link<Self> {
                let nn = self.child[dir].take();
                self.fix();
                nn
            }
            fn set(&mut self, dir: usize, node: Link<Self> ) {
                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<N> = Option<Box<N>>;

pub trait Node: Sized {
    type Value;
    fn push(&mut self);
    fn fix(&mut self);
    fn child(&self, dir: usize) -> &Link<Self>;
    fn child_mut(&mut self, dir: usize) -> &mut Link<Self>;
    fn take(&mut self, dir: usize) -> Link<Self>;
    fn set(&mut self, dir: usize, node: Link<Self>);
    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, <Self as Node>::Value: Monoid {
    fn fold(&self) -> <Self as Node>::Value;
}

pub fn size<N: SizeNode>(link: &Link<N>) -> usize {
    match *link {
        Some(ref node) => node.size(),
        None => 0,
    }
}
pub fn fold<N: FoldNode>(link: &Link<N>) -> <N as Node>::Value where <N as Node>::Value: Monoid {
    match *link {
        Some(ref node) => node.fold(),
        None => <N as Node>::Value::identity(),
    }
}

use std::cmp::Ordering::{ Equal, Greater, Less };

pub trait SplayArrayNode: Node + SizeNode {}
impl<N: Node + SizeNode> SplayArrayNode for N {}

fn depth_fix<N: SplayArrayNode>(n: &mut Link<N>, dir: usize) {
    if let Some(ref mut x) = n {
        depth_fix(x.as_mut().child_mut(dir), dir);
        x.as_mut().fix();
    }
}

fn splay<N: SplayArrayNode>(mut root: Box<N>, mut i: usize) -> Box<N> {
    let mut top_left: Link<N> = None;
    let mut top_right: Link<N> = 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<N: SplayArrayNode>(x: Link<N>, y: Link<N>) -> Link<N> {
    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<N: SplayArrayNode>(x: Link<N>, i: usize) -> (Link<N>, Link<N>) {
    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<N: SplayArrayNode> {
    root: Link<N>,
}

impl<N: SplayArrayNode> SplayArray<N> {
    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<usize>) -> 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<N: SplayArrayNode + FoldNode> SplayArray<N> where N::Value: Monoid {
    pub fn fold(&self) -> N::Value { fold(&self.root) }
}

impl<N: SplayArrayNode + ReversibleNode> SplayArray<N> {
    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<N>,
    left: SplayArray<N>,
    center: SplayArray<N>,
    right: SplayArray<N>,
}

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<N> { 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);
        }
    }
}
yukicoder

結果

テストケース

ソースコード
