AtCoder Beginner Contest 415 F

https://atcoder.jp/contests/abc415/tasks/abc415_f

二分木を使って、各ノードに左端からどの文字が何文字連続しているか、それに右端とそれ以外も保持しておきます。

// Max Combo
#![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 ////////////////////

#[derive(Copy, Clone, Debug)]
enum MaxPos {
    Left,
    Mid,
    Right,
    Whole,
}

#[derive(Copy, Clone, Debug)]
struct Node {
    left: (char, usize),
    mid: (char, usize),
    right: (char, usize),
    maxpos: MaxPos
}

impl Node {
    fn max_len(&self) -> usize {
        match self.maxpos {
            MaxPos::Left => self.left.1,
            MaxPos::Mid  => self.mid.1,
            _            => self.right.1
        }
    }
    
    fn is_whole(&self) -> bool {
        match self.maxpos {
            MaxPos::Whole => true,
            _             => false
        }
    }
    
    fn join(rng1: Node, rng2: Node) -> Node {
        if rng1.is_whole() && rng2.is_whole() && rng1.left.0 == rng2.left.0 {
            let rng = (rng1.left.0, rng1.left.1 + rng2.left.1);
            Node::new(rng, rng, rng, MaxPos::Whole)
        }
        else if rng1.right.0 != rng2.left.0 {
            if rng1.max_len() >= rng2.max_len() {
                match rng1.maxpos {
                    MaxPos::Mid   => Node::new(rng1.left, rng1.mid,
                                                rng2.right, MaxPos::Mid),
                    MaxPos::Right => Node::new(rng1.left, rng1.right,
                                                rng2.right, MaxPos::Mid),
                    _             => Node::new(rng1.left, rng1.mid,
                                                rng2.right, MaxPos::Left),
                }
            }
            else {
                match rng2.maxpos {
                    MaxPos::Mid   => Node::new(rng1.left, rng2.mid,
                                                rng2.right, MaxPos::Mid),
                    MaxPos::Left  => Node::new(rng1.left, rng2.left,
                                                rng2.right, MaxPos::Mid),
                    _             => Node::new(rng1.left, rng2.mid,
                                                rng2.right, MaxPos::Right),
                }
            }
        }
        else {
            let new_mid = (rng1.right.0, rng1.right.1 + rng2.left.1);
            if new_mid.1 > rng1.max_len() && new_mid.1 > rng2.max_len() {
                if rng1.is_whole() {
                    Node::new(new_mid, new_mid, rng2.right, MaxPos::Left)
                }
                else if rng2.is_whole() {
                    Node::new(rng1.left, new_mid, new_mid, MaxPos::Right)
                }
                else {
                    Node::new(rng1.left, new_mid, rng2.right, MaxPos::Mid)
                }
            }
            else if rng1.max_len() >= rng2.max_len() {
                if rng1.left.1 >= rng1.mid.1 {
                    Node::new(rng1.left, new_mid, rng2.right, MaxPos::Left)
                }
                else {
                    Node::new(rng1.left, rng1.mid, rng2.right, MaxPos::Mid)
                }
            }
            else {
                if rng2.mid.1 <= rng2.right.1 {
                    Node::new(rng1.left, new_mid, rng2.right, MaxPos::Right)
                }
                else {
                    Node::new(rng1.left, rng2.mid, rng2.right, MaxPos::Mid)
                }
            }
        }
    }
    
    fn new(left: (char, usize), mid: (char, usize),
                    right: (char, usize), maxpos: MaxPos) -> Node {
        Node { left, mid, right, maxpos }
    }
    
    fn empty() -> Node {
        Node::new(('a', 0), ('a', 0), ('a', 0), MaxPos::Whole)
    }
    
    fn one(c: char) -> Node {
        Node::new((c, 1), (c, 1), (c, 1), MaxPos::Whole)
    }
}


//////////////////// Segment Tree ////////////////////

type Range = (usize, usize);

struct SegmentTree {
    n: usize,
    v: Vec<Node>,
}

impl SegmentTree {
    fn max(&self, rng: Range) -> usize {
        let node = self.max_core(rng, 0, self.n, 0);
        node.max_len()
    }
    
    fn max_core(&self, rng: Range, first: usize,
                                last: usize, i: usize) -> Node {
        if rng.0 <= first && last <= rng.1 {
            self.v[i]
        }
        else {
            let mid = (first + last) / 2;
            if rng.1 <= mid {
                self.max_core(rng, first, mid, i*2+1)
            }
            else if rng.0 >= mid {
                self.max_core(rng, mid, last, i*2+2)
            }
            else {
                Node::join(self.max_core(rng, first, mid, i*2+1),
                           self.max_core(rng, mid, last, i*2+2))
            }
        }
    }
    
    fn update(&mut self, i: usize, c: char) {
        self.update_core(self.n - 1 + i, c)
    }
    
    fn update_core(&mut self, mut i: usize, c: char) {
        loop {
            if i < self.n - 1 {
                self.v[i] = Node::join(self.v[i*2+1], self.v[i*2+2])
            }
            else {
                self.v[i] = Node::one(c)
            }
            if i == 0 {
                break
            }
            i = (i - 1) / 2
        }
    }
    
    fn ceil_two_pow(n: usize) -> usize {
        if n == 1 { 1 } else { SegmentTree::ceil_two_pow((n+1)/2) * 2 }
    }
    
    fn create(s: String) -> SegmentTree {
        let m = s.len();
        let cs: Vec<char> =  s.chars().collect();
        let n = SegmentTree::ceil_two_pow(m);
        let mut v: Vec<Node> = vec![Node::empty(); n*2-1];
        for i in (0..m+n-1).rev() {
            if i >= n - 1 {     // leaf
                v[i] = Node::one(cs[i+1-n])
            }
            else {
                v[i] = Node::join(v[i*2+1], v[i*2+2])
            }
        }
        SegmentTree { n, v }
    }
}


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

enum Query {
    Update(usize, char),
    Print((usize, usize)),
}

impl Query {
    fn read() -> Query {
        let v: Vec<String> = read_vec();
        if v[0] == "1" {
            Query::Update(v[1].parse::<usize>().unwrap() - 1,
                            v[2].chars().next().unwrap())
        }
        else {
            Query::Print((v[1].parse::<usize>().unwrap() - 1,
                            v[2].parse::<usize>().unwrap()))
        }
    }
}


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

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

fn F(S: String, Q: usize) {
    let mut tree = SegmentTree::create(S);
    for _ in 0..Q {
        match Query::read() {
            Query::Update(i, c) => tree.update(i, c),
            Query::Print(rng) => println!("{}", tree.max(rng))
        }
    }
}

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