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) }