AtCoder Beginner Contest 430 F

https://atcoder.jp/contests/abc430/tasks/abc430_f

入力例の最初のケースだと、

  1 2
4 3 2
4 5

という位置関係なので、1は右端には行けません。2は左に3個はあるので、4番目以降になります。
なので、木を作って指定した範囲に1を足せるようにするとよいです。

// Back and Forth Filling
#![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()
}


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

type Node = i32;
type Range = (usize, usize);
type NodeRange = (usize, usize, usize);     // (first, last, index)

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

impl SegmentTree {
    fn ceil_two_pow(n: usize) -> usize {
        if n == 1 { 1 } else { SegmentTree::ceil_two_pow((n+1)/2) * 2 }
    }
    
    fn add_core(&mut self, rng: Range, (first, last, n): NodeRange) {
        if rng.0 <= first && last <= rng.1 {
            self.v[n] += 1
        }
        else {
            let mid = (first + last) / 2;
            if rng.0 < mid {
                self.add_core(rng, (first, mid, n*2+1))
            }
            if mid < rng.1 {
                self.add_core(rng, (mid, last, n*2+2))
            }
        }
    }
    
    fn add(&mut self, first: usize, last: usize) {
        self.add_core((first, last), (0, self.n, 0))
    }
    
    fn to_vec_core(&self, v: &mut Vec<Node>, rng: Range,
                    offs: usize, a: Node, (first, last, n): NodeRange) {
        if last - first == 1 {
            v[first-offs] = self.v[n] + a
        }
        else {
            let mid = (first + last) / 2;
            if rng.0 < mid {
                self.to_vec_core(v, rng, offs, a+self.v[n], (first, mid, n*2+1))
            }
            if mid < rng.1 {
                self.to_vec_core(v, rng, offs, a+self.v[n], (mid, last, n*2+2))
            }
        }
    }
    
    fn to_vec(&self, first: usize, last: usize) -> Vec<Node> {
        let mut v: Vec<Node> = vec![0; last - first];
        self.to_vec_core(&mut v, (first, last), first, 0, (0, self.n, 0));
        v
    }
    
    fn create(m: usize) -> SegmentTree {
        let n = SegmentTree::ceil_two_pow(m);
        let v: Vec<Node> = vec![0; n*2-1];
        SegmentTree { n, v }
    }
}


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

fn groupby(S: &String) -> Vec<(char, usize)> {
    let mut v: Vec<(char, usize)> = vec![];
    let cs: Vec<char> = S.chars().collect();
    let mut prev_c = '.';
    let mut len = 0;
    for c in cs {
        if len == 0  || c == prev_c {
            len += 1
        }
        else {
            v.push((prev_c, len));
            len = 1
        }
        prev_c = c
    }
    v.push((prev_c, len));
    v
}

fn add_range(i: usize, j: usize, v: &Vec<(char, usize)>) -> (usize, usize) {
    let (c, n) = v[i];
    let (p, q) = if i == 0 && j == 0 {
        (0, n)
    }
    else if j == 0 {
        (0, v[i-1].1 + n)
    }
    else if j == n {
        (n, 0)
    }
    else {
        (j, n - j)
    };
    
    if c == 'R' { (p, q) } else { (q, p) }
}

fn F_each(N: usize, S: String) {
    let mut tree = SegmentTree::create(N);
    let v = groupby(&S);
    let L = v.len();
    for i in 0..L {
        let n = v[i].1;
        let l = if i < L - 1 { n } else { n + 1 };
        for j in 0..l {
            let (d, e) = add_range(i, j, &v);
            tree.add(d, N - e);
        }
    }
    let w = tree.to_vec(0, N);
    println!("{}", w.iter().map(|a| a.to_string()).
                            collect::<Vec<String>>().join(" "))
}

fn F(T: usize) {
    for _ in 0..T {
        let N: usize = read();
        let S: String = read();
        F_each(N, S)
    }
}

fn main() {
    let T: usize = read();
    F(T)
}