AtCoder Beginner Contest 322 F

https://atcoder.jp/contests/abc322/tasks/abc322_f

木を作ってノードにparityをつけて、丸ごと反転するならparityを反転するだけ、という具合に考え方は簡単なんですが。
Rustは、固定の木だとまだなんとかなりますね。

// Vacation Query
#![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()
}


//////////////////// Node ////////////////////

type Conts = Vec<(usize, bool)>;

struct Node {
    first: usize,
    last: usize,
    parity: bool,
    conts: Conts,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
}

impl Node {
    fn new(bs: &Vec<bool>, first: usize, last: usize) -> Self {
        if last - first == 1 {
            let conts = vec![(1, bs[first as usize])];
            return Node { first, last, parity: false, conts,
                                    left: None, right: None };
        }
        
        let mid = (first + last) / 2;
        let left = Node::new(bs, first, mid);
        let right = Node::new(bs, mid, last);
        let conts = Node::join(left.get_conts(),
                               Node::join_end_conts(&left, &right),
                               right.get_conts());
        Node { first, last, parity: false, conts, left: Some(Box::new(left)),
                                                right: Some(Box::new(right)) }
    }
    
    fn is_leaf(&self) -> bool {
        self.last - self.first == 1
    }
    
    fn get_conts(&self) -> Conts {
        if self.parity {
            self.conts.iter().map(|(n, b)| (*n, !b)).collect::<Conts>()
        } else {
            self.conts.to_vec()
        }
    }

    fn join(left_conts: Conts, end_conts: Conts, right_conts: Conts) -> Conts {
        let mut conts = vec![];
        conts.extend_from_slice(&left_conts[..left_conts.len() - 1]);
        conts.extend_from_slice(&end_conts);
        conts.extend_from_slice(&right_conts[1..]);
        if conts.len() <= 3 {
            return conts;
        }
        let mut conts1 = vec![];
        let mut conts2 = vec![];
        for (n, b) in &conts[1..conts.len() - 1] {
            if *b {
                conts1.push((*n, *b));
            } else {
                conts2.push((*n, *b));
            }
        }
        let max_cont1 = match conts1.iter().max_by_key(|(n, _)| n) {
            Some((n, b)) => vec![(*n, *b)],
            None => vec![],
        };
        let max_cont2 = match conts2.iter().max_by_key(|(n, _)| n) {
            Some((n, b)) => vec![(*n, *b)],
            None => vec![],
        };
        let mut new_conts = vec![];
        new_conts.push(conts[0]);
        new_conts.extend_from_slice(&max_cont1);
        new_conts.extend_from_slice(&max_cont2);
        new_conts.push(conts[conts.len() - 1]);
        new_conts
    }

    fn join_end_conts(left: &Node, right: &Node) -> Conts {
        let (n1, b1) = left.get_conts()[left.get_conts().len() - 1];
        let (n2, b2) = right.get_conts()[0];
        if b1 == b2 {
            vec![(n1 + n2, b1)]
        } else {
            vec![(n1, b1), (n2, b2)]
        }
    }
    
    fn inverse(&mut self, first: usize, last: usize) {
        if self.is_leaf() || (first <= self.first && self.last <= last) {
            self.parity = !self.parity;
            return
        }

        let mid = (self.first + self.last) / 2;
        if first < mid {
            if let Some(left) = &mut self.left {
                left.inverse(first, last);
            }
        }
        if mid < last {
            if let Some(right) = &mut self.right {
                right.inverse(first, last);
            }
        }
        // Assuming get_conts and join_end_conts are methods of Node
        if let (Some(left), Some(right)) = (&self.left, &self.right) {
            self.conts = Node::join(left.get_conts(),
                                    Node::join_end_conts(&left, &right),
                                    right.get_conts());
        }
    }
    
    fn get_conts_range(&self, first: usize, last: usize) -> Conts {
        if self.is_leaf() || (first <= self.first && self.last <= last) {
            return self.get_conts()
        }
        
        let mid = (self.first + self.last) / 2;
        let conts1 = if first < mid {
            let left = self.left.as_ref().unwrap();
            left.get_conts_range(first, last)
        }
        else {
            vec![]
        };
        let conts2 = if mid < last {
            let right = self.right.as_ref().unwrap();
            right.get_conts_range(first, last)
        }
        else {
            vec![]
        };
        
        let conts: Conts;
        if conts1.is_empty() {
            conts = conts2
        }
        else if conts2.is_empty() {
            conts = conts1
        }
        else {
            let (n1, b1) = conts1.last().unwrap().clone();
            let (n2, b2) = conts2.first().unwrap().clone();
            if b1 == b2 {
                let mut new_conts1 = conts1.clone();
                new_conts1.pop();
                let mut new_conts2 = conts2.clone();
                new_conts2.remove(0);
                conts = [new_conts1, vec![(n1 + n2, b1)], new_conts2].concat();
            } else {
                conts = [conts1.clone(), conts2.clone()].concat();
            }
        }
        
        if self.parity {
            conts.into_iter().map(|(n, b)| (n, !b)).collect::<Conts>()
        }
        else {
            conts
        }
    }
    
    fn get_longest_ones(&self, first: usize, last: usize) -> usize {
        let conts = self.get_conts_range(first, last);
        let lengths_one: Vec<usize> = conts.into_iter().filter(|&(_n, b)| b).
                                                    map(|(n, _b)| n).collect();
        match lengths_one.into_iter().max() {
            Some(l) => l,
            None    => 0
        }
    }
    
    fn string(&self) -> String {
        if self.is_leaf() {
            let (_n, b) = self.get_conts()[0];
            format!("{}", if b { 1 } else { 0 })
        }
        else {
            let s1 = self.left.as_ref().unwrap().string();
            let s2 = self.right.as_ref().unwrap().string();
            let s = s1 + &s2;
            if self.parity {
                s.chars().map(|c| if c == '0' { '1' } else { '0' }).
                                                        collect::<String>()
            }
            else {
                s
            }
        }
    }
}


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

type Query = (usize, usize, usize);

fn read_query() -> Query {
    let v = read_vec();
    let (c, L, R) = (v[0], v[1], v[2]);
    (c, L, R)
}

fn read_input() -> (String, Vec<Query>) {
    let v: Vec<usize> = read_vec();
    let Q = v[1];
    let S: String = read();
    let queries: Vec<Query> = (0..Q).map(|_| read_query()).collect();
    (S, queries)
}

fn F(S: String, queries: Vec<Query>) {
    let bs: Vec<bool> = S.chars().map(|c| c == '1').collect();
    let mut tree = Node::new(&bs, 0, S.len());
    for (c, L, R) in queries.into_iter() {
        if c == 1 {
            tree.inverse(L-1, R);
        }
        else {
            println!("{}", tree.get_longest_ones(L-1, R))
        }
    }
}

fn main() {
    let (S, queries) = read_input();
    F(S, queries)
}