Count Cells in a Window の解説

マス(1, 1) ~ マス(i, j)の長方形の中の黒マスをS(i, j)とすると

求める答えは

S(b, d) + S(a - 1, c - 1) - S(b, c - 1) - S(a - 1, d)

となる。

クエリ先読みして、予め必要なクエリを各行ごとにまとめておく。

その上で行の上から処理していく。 i行目の操作は以下の通り

• LR[i]を区間加算
• i行目のj列目までの黒総和の区間取得

よってLazySegTreeにてできますよね。

#[derive(Debug, Clone, Copy)]
struct M {
    value: usize,
    size: usize,
}

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

struct F;
impl MapMonoid for F {
    type M = M;
    type F = usize;
    fn identity_map() -> Self::F {
        0
    }
    fn mapping(f: &Self::F, x: &<Self::M as Monoid>::S) -> <Self::M as Monoid>::S {
        M {
            value: x.value + x.size * f,
            size: x.size,
        }
    }
    fn composition(f: &Self::F, g: &Self::F) -> Self::F {
        *f + *g
    }
}

fn main() {
    input! {
        n: usize, m: usize, q: usize,
        lr: [(usize, usize); n],
        abcd: [(usize, usize, usize, usize); q]
    }
    let mut seg = {
        let mut seg = LazySegtree::<F>::new(m + 1);
        for i in 0..=m {
            seg.set(i, M { value: 0, size: 1 });
        }
        seg
    };
    let query = {
        let mut query = vec![vec![]; n + 1];
        for &(a, b, c, d) in abcd.iter() {
            query[b].push(d);
            query[b].push(c - 1);
            query[a - 1].push(d);
            query[a - 1].push(c - 1);
        }
        query
    };
    let queryans = {
        let mut map = HashMap::new();
        for i in 0..=n {
            if i >= 1 {
                let (l, r) = lr[i - 1];
                seg.apply_range(l..=r, 1);
            }
            for &j in query[i].iter() {
                let count = seg.prod(..=j).value;
                map.insert((i, j), count);
            }
        }
        map
    };
    let get = |i: usize, j: usize| queryans.get(&(i, j)).unwrap();
    let ans = abcd
        .iter()
        .map(|&(a, b, c, d)| {
            let a1 = get(b, d);
            let a2 = get(b, c - 1);
            let a3 = get(a - 1, d);
            let a4 = get(a - 1, c - 1);
            a1 + a4 - a2 - a3
        })
        .join("\n");
    println!("{}", ans);
}