AtCoder Beginner Contest 381 E

https://atcoder.jp/contests/abc381/tasks/abc381_e

/の前後で1と2を数を数えますが、2の数が1の数以上になる右端の/の位置を二分探索して、それとそれより一つ左を比べます。

// 11/22 Subsequence
#![allow(non_snake_case)]

use std::cmp::{min, max};


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


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

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

type Query = (usize, usize);

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

fn accumulate(c: char, chars: &Vec<char>) -> Vec<i32> {
    let mut acc: Vec<i32> = vec![];
    for &c1 in chars.iter() {
        let inc: i32 = if c1 == c { 1 } else { 0 };
        match acc.iter().last() {
            Some(&a) => acc.push(a + inc),
            None     => acc.push(inc)
        }
    }
    acc
}

fn accumulate_back(c: char, chars: &Vec<char>) -> Vec<i32> {
    let mut acc: Vec<i32> = vec![];
    for &c1 in chars.iter().rev() {
        let inc: i32 = if c1 == c { 1 } else { 0 };
        match acc.iter().last() {
            Some(&a) => acc.push(a + inc),
            None     => acc.push(inc)
        }
    }
    acc.into_iter().rev().collect::<Vec<i32>>()
}

// 与えられた位置から最初に見つかった位置の添え字
fn find_pos(p: usize, ps: &Vec<usize>) -> usize {
    if ps.len() == 0 {
        return 0
    }
    
    let mut first: usize = 0;
    let mut last: usize = ps.len();
    while last - first > 2 {
        let mid = (first + last) / 2;
        if ps[mid] >  p {
            last = mid + 1
        }
        else {
            first = mid
        }
    }
    if ps[first] >= p {
        first
    }
    else if first + 1 < ps.len() && ps[first+1] >= p {
        first + 1
    }
    else {
        ps.len()
    }
}

fn count_ones(first: usize, last: usize, ones: &Vec<i32>) -> i32 {
    // lastには/があるはずだからindexをlastとしてもよい
    if first == 0 {
        ones[last]
    }
    else {
        ones[last] - ones[first-1]
    }
}

fn count_twos(first: usize, last: usize, twos: &Vec<i32>) -> i32 {
    if last == twos.len() {
        twos[first]
    }
    else {
        twos[first] - twos[last]
    }
}

// 2の数が1の数以上になる左端
fn leftmost(mut first: usize, mut last: usize, L: usize, R: usize,
            slash_pos: &Vec<usize>, ones: &Vec<i32>, twos: &Vec<i32>) -> usize {
    let f = |x: usize| -> bool {
        let p = slash_pos[x];
        count_ones(L, p, ones) <= count_twos(p, R, twos)    
    };
    
    while last - first > 1 {
        let mid = (first + last) / 2;
        if f(mid) {
            first = mid
        }
        else {
            last = mid
        }
    }
    
    if !f(first) {
        usize::MAX
    }
    else {
        first
    }
}

fn F(Q: usize, S: String) {
    let N = S.len();
    let chars: Vec<char> = S.chars().collect();
    let slash_pos: Vec<usize> = (0..N).filter(|&i| chars[i] == '/').collect();
    let ones = accumulate('1', &chars);
    let twos = accumulate_back('2', &chars);
    let queries: Vec<Query> = (0..Q).map(|_| read_query()).collect();
    for (L, R) in queries.into_iter() {
        let first = find_pos(L, &slash_pos);
        let last = find_pos(R, &slash_pos);
        if last - first == 0 {
            println!("0");
            continue
        }
        let p = leftmost(first, last, L, R, &slash_pos, &ones, &twos);
        let q = if p == usize::MAX {
            first
        }
        else if p == slash_pos.len() {
            last - 1
        }
        else {
            p
        };
        let pos = slash_pos[q];
        let n1 = count_ones(L, pos, &ones);
        let n2 = count_twos(pos, R, &twos);
        let mut n = min(n1, n2);
        if q + 1 < slash_pos.len() {
            let pos1 = slash_pos[q+1];
            let n3 = count_ones(L, pos1, &ones);
            let n4 = count_twos(pos1, R, &twos);
            n = max(n, min(n3, n4))
        }
        println!("{}", n * 2 + 1)
    }
}

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