AtCoder Beginner Contest 461 E

https://atcoder.jp/contests/abc461/tasks/abc461_e

入力例1で考えると、1行目を黒く塗って+3、3行目を黒く塗って+3、2列目を白く塗るのですが、黒が2つあるので-2、最後に1行目を黒く塗るのですが、1回目のクエリで1行目を塗ってあるので、その間に列を1回塗っているので+1です。
このように、前に塗った場所から今の場所までで行か列をカウントすればよいです。なのでそのような木を作ります。

// liter
#![allow(non_snake_case)]


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}


//////////////////// Dir ////////////////////

#[derive(Eq, Hash, PartialEq, Clone)]
enum Dir {
    Row,
    Col
}


//////////////////// Query ////////////////////

type Query = (Dir, usize);

fn read_query() -> Query {
    let v: Vec<usize> = read_vec();
    match v[0] {
        1 => (Dir::Row, v[1]-1),
        _ => (Dir::Col, v[1]-1),
    }
}


//////////////////// SegTree ////////////////////

trait Monoid {
    type S: Clone;
    fn op(a: &Self::S, b: &Self::S) -> Self::S;
    fn e() -> Self::S;
}

struct SegTree<M: Monoid> {
    n: usize,
    size: usize,
    data: Vec<M::S>,
}

impl<M: Monoid> SegTree<M> {
    fn is_leaf(&self, i: usize) -> bool {
        i >= self.size - 1
    }
    
    fn new(n: usize) -> Self {
        let size = n.next_power_of_two();
        SegTree {
            n,
            size,
            data: vec![M::e(); size*2-1],
        }
    }
    
    fn from(v: Vec<M::S>) -> Self {
        let n = v.len();
        let size = n.next_power_of_two();
        let mut data = vec![M::e(); size*2-1];
        for i in 0..n {
            data[i+size-1] = v[i].clone();
        }
        let mut seg = SegTree { n, size, data };
        for i in (0..size-1).rev() {
            seg.data[i] = M::op(&seg.data[2*i+1], &seg.data[2*i+2]);
        }
        seg
    }
    
    fn set(&mut self, mut i: usize, x: M::S) {
        i = i + self.size - 1;
        self.data[i] = x;
        while i != 0 {
            i = (i - 1) / 2;
            self.data[i] = M::op(&self.data[2*i+1], &self.data[2*i+2]);
        }
    }
    
    fn prod(&self, mut l: usize, mut r: usize) -> M::S {
        let mut sml = M::e();
        let mut smr = M::e();
        l = l + self.size - 1;
        r = r + self.size - 1;
        while l < r {
            if l % 2 == 0 {
                sml = M::op(&sml, &self.data[l]);
                l += 1;
            }
            if r % 2 == 0 {
                r -= 1;
                smr = M::op(&self.data[r], &smr);
            }
            l = (l - 1) / 2;
            r = (r - 1) / 2
        }
        M::op(&sml, &smr)
    }
    
    fn get(&self, i: usize) -> M::S {
        self.data[i+self.size-1].clone()
    }
}


//////////////////// Monoid ////////////////////

struct Sum;
impl Monoid for Sum {
    type S = (usize, usize);    // (rowのcounter, colのcounter)
    fn op((m1, n1): &Self::S, (m2, n2): &Self::S) -> Self::S {
        (m1 + m2, n1 + n2)
    }
    fn e() -> Self::S { (0, 0) }
}


//////////////////// Tree ////////////////////

use std::collections::HashMap;

struct Tree {
    N: usize,
    seg: SegTree::<Sum>,
    m: HashMap<(Dir, usize), usize>,
    last: usize
}

impl Tree {
    fn new(N: usize, Q: usize) -> Tree {
        let seg = SegTree::new(Q);
        let m: HashMap<(Dir, usize), usize> = HashMap::new();
        Tree { N, seg, m, last: 0 }
    }
    
    fn paint(&mut self, p: (Dir, usize)) -> i64 {
        let first = self.m.get(&p).map(|&v| v+1).unwrap_or(0);
        let (m, n) = self.seg.prod(first, self.last);
        self.m.insert(p.clone(), self.last);
        match p {
            (Dir::Row, _) => self.seg.set(self.last, (1, 0)),
            (Dir::Col, _) => self.seg.set(self.last, (0, 1))
        }
        self.last += 1;
        if first != 0 {
            self.seg.set(first - 1, (0, 0));
            match p {
                (Dir::Row, _) => n as i64,
                (Dir::Col, _) => -(m as i64)
            }
        }
        else {
            match p {
                (Dir::Row, _) => self.N as i64,
                (Dir::Col, _) => -(m as i64)
            }
        }
    }
}


//////////////////// process ////////////////////

fn read_input() -> (usize, usize) {
    let v: Vec<usize> = read_vec();
    let (N, Q) = (v[0], v[1]);
    (N, Q)
}

fn F(N: usize, Q: usize) {
    let mut tree = Tree::new(N, Q);
    let mut counter: i64 = 0;
    for _ in 0..Q {
        let query = read_query();
        counter += tree.paint(query);
        println!("{}", counter)
    }
}

fn main() {
    let (N, Q) = read_input();
    F(N, Q)
}