AtCoder Beginner Contest 429 F

https://atcoder.jp/contests/abc429/tasks/abc429_f

横方向に領域を分割していきます。最後まで分割したら、隣の領域同士を結合して木を作ります。各ノードは左端の各行から右端の各行までの最短距離(+1)を記録しておけばよいので、簡単に結合できます。ルートを見れば(1, 1)から(3, N)の最短距離が分かります。各クエリではO(logN)個のノードだけ更新すればよいです。

// Shortest Path 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 Node = [[i32; 3]; 3];

fn connect(u: Node, v: Node) -> Node {
    let mut w: Node = [[-1; 3]; 3];
    for i in 0..3 {
        for j in 0..3 {
            let mut d: i32 = -1;
            for k in 0..3 {
                if u[i][k] != -1 && v[k][j] != -1 {
                    let d1 = u[i][k] + v[k][j];
                    if d == -1 || d1 < d {
                        d = d1
                    }
                }
            }
            w[i][j] = d
        }
    }
    w
}


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

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

impl SegmentTree {
    fn to_flags(a: Node) -> i32 {
        let mut flags: i32 = 0;
        for j in 0..3 {
            if a[j][j] == 1 {
                flags |= 1 << j
            }
        }
        flags
    }
    
    fn initialize(j: usize, k: usize, flags: i32) -> i32 {
        if k == j {
            if ((flags >> j) & 1) == 1 { 1 } else { -1 }
        }
        else if k == j + 1 || k + 1 == j {
            let mask = (1 << j) | (1 << k);
            if (flags & mask) == mask { 2 } else { -1 }
        }
        else {  // 0と2
            if flags == 7 { 3 } else { -1 }
        }
    }
    
    fn to_node(flags: i32) -> Node {
        let mut node = [[-1; 3]; 3];
        for j in 0..3 {
            for k in 0..3 {
                node[j][k] = SegmentTree::initialize(j, k, flags)
            }
        }
        node
    }
    
    fn change(&mut self, r: usize, c: usize) {
        let mut i = c + self.n - 1;
        let mut flags = SegmentTree::to_flags(self.v[i]);
        flags ^= 1 << r;
        self.v[i] = SegmentTree::to_node(flags);
        while i > 0 {
            i = (i - 1) / 2;
            self.v[i] = connect(self.v[i*2+1], self.v[i*2+2])
        }
    }
    
    fn dist(&self) -> i32 {
        let d = self.v[0][0][2];
        if d == -1 { -1 } else { d - 1 }
    }
    
    fn ceil_two_pow(n: usize) -> usize {
        if n == 1 { 1 } else { SegmentTree::ceil_two_pow((n+1)/2) * 2 }
    }
    
    fn create(S: [String; 3]) -> SegmentTree {
        let L = S[0].len();
        let n = SegmentTree::ceil_two_pow(L);
        let mut v: Vec<Node> = vec![[[-1; 3]; 3]; n*2-1];
        let mut chars: Vec<Vec<char>> = vec![vec![]; 3];
        for j in 0..3 {
            chars[j] = S[j].chars().collect::<Vec<char>>()
        }
        
        for i in 0..L {
            let mut flags: i32 = 0;
            for j in 0..3 {
                if chars[j][i] == '.' {
                    flags |= 1 << j
                }
            }
            
            v[i+n-1] = SegmentTree::to_node(flags);
        }
        
        // 余り分はオープン
        for i in L..n {
            v[i+n-1] = [[0, 1, 2], [1, 0, 1], [2, 1, 0]]
        }
        
        // 結合していく
        for i in (0..n-1).rev() {
            v[i] = connect(v[i*2+1], v[i*2+2])
        }
        
        SegmentTree { n, v }
    }
}


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

fn read_query() -> (usize, usize) {
    let v: Vec<usize> = read_vec();
    let (r, c) = (v[0]-1, v[1]-1);
    (r, c)
}


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

fn read_input() -> ([String; 3], usize) {
    let _N: usize = read();
    let S: [String; 3] = [read(), read(), read()];
    let Q: usize = read();
    (S, Q)
}

fn F(S: [String; 3], Q: usize) {
    let mut tree = SegmentTree::create(S);
    for _ in 0..Q {
        let (r, c) = read_query();
        tree.change(r, c);
        println!("{}", tree.dist())
    }
}

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