AtCoder Beginner Contest 419 D

https://atcoder.jp/contests/abc419/tasks/abc419_d

木を作って指定した範囲に1を足して、最後に偶数ならS側の文字です。

// Substr Swap
#![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()
}


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

type Value = i32;   // 何回反転したか
type Range = (usize, usize);

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

impl SegmentTree {
    fn inverse(&mut self, rng: Range) {
        self.inverse_core(rng, 0, self.n, 0)
    }
    
    fn inverse_core(&mut self, rng: Range,
                            first: usize, last: usize, i: usize) {
        if rng.0 <= first && last <= rng.1 {
            self.v[i] += 1
        }
        else {
            let mid = (first + last) / 2;
            if rng.1 <= mid {
                self.inverse_core(rng, first, mid, i*2+1)
            }
            else if rng.0 >= mid {
                self.inverse_core(rng, mid, last, i*2+2)
            }
            else {
                self.inverse_core(rng, first, mid, i*2+1);
                self.inverse_core(rng, mid, last, i*2+2);
            }
        }
    }
    
    fn to_list(&self, m: usize) -> Vec<bool> {
        let mut A: Vec<bool> = vec![false; m];
        self.to_list_core((0, m), 0, self.n, 0, 0, &mut A);
        A
    }
    
    fn to_list_core(&self, rng: Range, first: usize, last: usize,
                                    i: usize, s: i32, A: &mut Vec<bool>) {
        if last - first == 1 {
            A[first] = ((s + self.v[i]) & 1) == 1
        }
        else {
            let mid = (first + last) / 2;
            let s1 = s + self.v[i];
            if rng.1 <= mid {
                self.to_list_core(rng, first, mid, i*2+1, s1, A)
            }
            else if rng.0 >= mid {
                self.to_list_core(rng, mid, last, i*2+2, s1, A)
            }
            else {
                self.to_list_core(rng, first, mid, i*2+1, s1, A);
                self.to_list_core(rng, mid, last, i*2+2, s1, A)
            }
        }
    }
    
    fn ceil_two_pow(n: usize) -> usize {
        if n == 1 { 1 } else { SegmentTree::ceil_two_pow((n+1)/2) * 2 }
    }
    
    fn create(m: usize) -> SegmentTree {
        let n = SegmentTree::ceil_two_pow(m);
        let v: Vec<Value> = vec![0; n*2-1];
        SegmentTree { n, v }
    }
}


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

fn read_range() -> Range {
    let v: Vec<usize> = read_vec();
    let (L, R) = (v[0], v[1]);
    (L - 1, R)
}

fn read_input() -> (String, String, Vec<Range>) {
    let v: Vec<usize> = read_vec();
    let M = v[1];
    let S: String = read();
    let T: String = read();
    let rngs: Vec<Range> = (0..M).map(|_| read_range()).collect();
    (S, T, rngs)
}

fn F(S: String, T: String, rngs: Vec<Range>) -> String {
    let cs1: Vec<char> = S.chars().collect();
    let cs2: Vec<char> = T.chars().collect();
    let N = cs1.len();
    let mut tree = SegmentTree::create(N);
    for rng in rngs {
        tree.inverse(rng)
    }
    let v = tree.to_list(N);
    (0..N).map(|i| if v[i] { cs2[i] } else { cs1[i] }).collect::<String>()
}

fn main() {
    let (S, T, rngs) = read_input();
    println!("{}", F(S, T, rngs))
}