せきがとまらない。

• モノクロデザイン (第七回 アルゴリズム実技検定:N問題) https://atcoder.jp/contests/past202107-open/tasks/past202107_n
  • 提出: https://atcoder.jp/contests/past202107-open/submissions/46499208
  • 解説 AC
  • 考察自体はできたが、うまく実装できず
  • x か y でソートして、座圧した y か x を遅延セグ木で持って反転させていけば良い
  • 処理済みの確定した面積を答えへと加算していけば良い

use lazysegtree::*;
use segtree::*;
use std::collections::{BTreeMap, BTreeSet};

use proconio::input;

fn main() {
    input! {
        q: usize,
        abcd: [(i64, i64, i64, i64); q],
    }

    let mut xs = BTreeSet::new();
    let mut lr = BTreeMap::new();
    for (a, b, c, d) in abcd {
        xs.insert(a);
        xs.insert(c);
        lr.entry(b).or_insert_with(Vec::new).push((a, c));
        lr.entry(d).or_insert_with(Vec::new).push((a, c));
    }
    let map = xs
        .into_iter()
        .enumerate()
        .fold(BTreeMap::new(), |mut m, (i, k)| {
            m.insert(k, i);
            m
        });
    let m = map.len();

    #[derive(Clone, Copy, Debug)]
    struct M(i64, i64);
    impl Monoid for M {
        type S = M;

        fn identity() -> Self::S {
            M(0, 0)
        }

        fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {
            M(a.0 + b.0, a.1 + b.1)
        }
    }

    #[derive(Clone, Copy, Debug)]
    struct F(bool);

    impl MapMonoid for F {
        type M = M;
        type F = F;

        fn identity_map() -> Self::F {
            F(false)
        }

        fn mapping(f: &Self::F, x: &<Self::M as Monoid>::S) -> <Self::M as Monoid>::S {
            if f.0 {
                M(x.1, x.0)
            } else {
                *x
            }
        }

        fn composition(f: &Self::F, g: &Self::F) -> Self::F {
            F(f.0 ^ g.0)
        }
    }

    let mut lst = LazySegtree::<F>::new(m - 1);
    let mut prev = map.iter();
    for (&x, &i) in map.iter().skip(1) {
        if let Some((p, _)) = prev.next() {
            lst.set(i - 1, M(0, x - p));
        }
    }

    for (_, lr) in lr.iter_mut() {
        lr.sort();
    }

    let mut ans = 0_i64;
    let mut next = lr.iter();
    let _ = next.next();
    for (y, lr) in lr.iter() {
        for (l, r) in lr {
            let l = map[l];
            let r = map[r];
            lst.apply_range(l..r, F(true));
        }

        if let Some((next_y, _)) = next.next() {
            ans += lst.all_prod().0 * (next_y - y);
        }
    }
    println!("{}", ans);
}

// lazysegtree

今日のコミット。

• rust-atcoder 1 commit
  • pastbook past202107_n