Skip to content

Rectangle union area

Rust

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
mod data_structure {
    /// 長方形 (xl, xr, yl, yr) の和集合の面積を求める。
    /// 各長方形は xl <= x < xr, yl <= y < yr の領域を表す。
    pub fn union_area(rects: &[(i64, i64, i64, i64)]) -> i64 {
        if rects.is_empty() {
            return 0;
        }

        // y座標を収集・座標圧縮
        let mut ys: Vec<i64> = Vec::with_capacity(rects.len() * 2);
        for &(_, _, yl, yr) in rects {
            ys.push(yl);
            ys.push(yr);
        }
        ys.sort();
        ys.dedup();

        let compress_y = |y: i64| -> usize { ys.binary_search(&y).unwrap() };

        // x方向のイベントを生成: (x座標, +1/-1, y区間)
        let mut events: Vec<(i64, i32, usize, usize)> = Vec::with_capacity(rects.len() * 2);
        for &(xl, xr, yl, yr) in rects {
            let cyl = compress_y(yl);
            let cyr = compress_y(yr);
            events.push((xl, 1, cyl, cyr));
            events.push((xr, -1, cyl, cyr));
        }
        events.sort();

        let mut seg = SegTree::new(&ys);

        let mut area: i64 = 0;
        let mut prev_x = events[0].0;

        for &(x, delta, yl, yr) in &events {
            // 前のx位置からここまでの面積を加算
            area += (x - prev_x) * seg.covered();
            prev_x = x;

            // y区間のcntを更新
            seg.add(yl, yr, delta);
        }

        area
    }

    /// スイープライン専用セグメントツリー
    /// 各リーフは圧縮後のy区間 [ys[i], ys[i+1]) に対応する。
    struct SegTree {
        n: usize,
        cnt: Vec<i32>,
        covered: Vec<i64>,
        /// 各リーフ区間の実際の長さ
        len: Vec<i64>,
    }

    impl SegTree {
        fn new(ys: &[i64]) -> Self {
            let m = ys.len() - 1; // 区間の数
            let n = m.next_power_of_two();

            let mut len = vec![0i64; 2 * n];
            for i in 0..m {
                len[n + i] = ys[i + 1] - ys[i];
            }
            for i in (1..n).rev() {
                len[i] = len[2 * i] + len[2 * i + 1];
            }

            Self {
                n,
                cnt: vec![0; 2 * n],
                covered: vec![0; 2 * n],
                len,
            }
        }

        fn covered(&self) -> i64 {
            self.covered[1]
        }

        /// 圧縮後の区間 [l, r) に delta を加算
        fn add(&mut self, l: usize, r: usize, delta: i32) {
            self.add_inner(1, 0, self.n, l, r, delta);
        }

        fn add_inner(
            &mut self,
            k: usize,
            seg_l: usize,
            seg_r: usize,
            l: usize,
            r: usize,
            delta: i32,
        ) {
            if seg_r <= l || r <= seg_l {
                return;
            }
            if l <= seg_l && seg_r <= r {
                self.cnt[k] += delta;
                self.pull(k);
                return;
            }
            let mid = (seg_l + seg_r) / 2;
            self.add_inner(2 * k, seg_l, mid, l, r, delta);
            self.add_inner(2 * k + 1, mid, seg_r, l, r, delta);
            self.pull(k);
        }

        fn pull(&mut self, k: usize) {
            if self.cnt[k] > 0 {
                self.covered[k] = self.len[k];
            } else if k >= self.n {
                self.covered[k] = 0;
            } else {
                self.covered[k] = self.covered[2 * k] + self.covered[2 * k + 1];
            }
        }
    }
}