遅延セグ木

[tipstar0125]

問題：https://atcoder.jp/contests/practice2/tasks/practice2_l 解答：https://atcoder.jp/contests/practice2/submissions/49333619 参考1：https://drken1215.hatenablog.com/entry/2023/11/18/030700 参考2：https://betrue12.hateblo.jp/entry/2020/09/22/194541 モノイドチートシート：https://betrue12.hateblo.jp/entry/2020/09/23/005940 ACL移植：https://github.com/tipstar0125/atcoder/issues/43#issuecomment-1891491608

input! {
    N: usize,
    Q: usize,
    A: [usize; N]
}

let mut seg: LazySegtree<InvMonoid> = A
    .iter()
    .map(|&x| {
        if x == 0 {
            Node {
                zero: 1,
                one: 0,
                inv: 0,
            }
        } else {
            Node {
                zero: 0,
                one: 1,
                inv: 0,
            }
        }
    })
    .collect::<Vec<_>>()
    .into();

for _ in 0..Q {
    input! {
        t: usize,
        l: usize1,
        r: usize1
    }
    if t == 1 {
        seg.apply_range(l..=r, true);
    } else {
        let ans = seg.prod(l..=r);
        println!("{}", ans.inv);
    }
}

• mapping: dataに対して、操作fを作用させる関数
  • 区間加算の場合、lazyには加算する値が入っており、これが操作f
• composition: これまでに溜めているlazyに対して、新しい操作を追加する関数
  • fの方が後の操作
  • これまでに溜めているgに、fを追加で操作(合成写像)

fn all_apply(&mut self, k: usize, f: F::F) {
    self.d[k] = F::mapping(&f, &self.d[k]);
    if k < self.size {
        self.lz[k] = F::composition(&f, &self.lz[k]);
    }
}
fn push(&mut self, k: usize) {
    self.all_apply(2 * k, self.lz[k].clone());
    self.all_apply(2 * k + 1, self.lz[k].clone());
    self.lz[k] = F::identity_map();
}

[tipstar0125]

区間反転更新・区間転倒数取得

#[derive(Clone, Copy)]
struct Node {
    zero: usize,
    one: usize,
    inv: usize,
}

struct InvMonoid;
impl Monoid for InvMonoid {
    type S = Node;
    fn identity() -> Self::S {
        Node {
            zero: 0,
            one: 0,
            inv: 0,
        }
    }
    fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {
        Node {
            zero: a.zero + b.zero,
            one: a.one + b.one,
            inv: a.inv + b.inv + a.one * b.zero,
        }
    }
}

impl MapMonoid for InvMonoid {
    type M = InvMonoid;
    type F = bool;
    fn identity_map() -> Self::F {
        false
    }
    fn mapping(&f: &bool, &x: &Node) -> Node {
        if f {
            Node {
                zero: x.one,
                one: x.zero,
                inv: x.zero * x.one - x.inv,
            }
        } else {
            x
        }
    }
    fn composition(&f: &bool, &g: &bool) -> bool {
        f ^ g
    }
}

[tipstar0125]

区間反転更新・区間和取得

問題：https://mojacoder.app/users/loop0919/problems/flip-puzzle 解答1：https://mojacoder.app/users/loop0919/problems/flip-puzzle/submissions/5a9c1301-74b1-438e-b605-21c784ec6887 解答2：https://mojacoder.app/users/loop0919/problems/flip-puzzle/submissions/29deabb3-10d3-40e1-b939-a0fd51b13b99

#[derive(Clone, Copy)]
struct Node {
    one: usize,
    size: usize,
}

struct M;
impl Monoid for M {
    type S = Node;
    fn identity() -> Self::S {
        Node { one: 0, size: 0 }
    }
    fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {
        Node {
            one: a.one + b.one,
            size: a.size + b.size,
        }
    }
}

impl MapMonoid for M {
    type M = M;
    type F = bool;
    fn identity_map() -> Self::F {
        false
    }
    fn mapping(&f: &bool, &x: &Node) -> Node {
        if f {
            Node {
                one: x.size - x.one,
                size: x.size,
            }
        } else {
            x
        }
    }
    fn composition(&f: &bool, &g: &bool) -> bool {
        f ^ g
    }
}

#[derive(Clone, Copy)]
struct Node {
    one: usize,
    zero: usize,
}

struct M;
impl Monoid for M {
    type S = Node;
    fn identity() -> Self::S {
        Node { one: 0, zero: 0 }
    }
    fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {
        Node {
            one: a.one + b.one,
            zero: a.zero + b.zero,
        }
    }
}

impl MapMonoid for M {
    type M = M;
    type F = bool;
    fn identity_map() -> Self::F {
        false
    }
    fn mapping(&f: &bool, &x: &Node) -> Node {
        if f {
            Node {
                one: x.zero,
                zero: x.one,
            }
        } else {
            x
        }
    }
    fn composition(&f: &bool, &g: &bool) -> bool {
        f ^ g
    }
}