A/AB Insertion の解説

Aを(, Bを)として考えた。 AかABしかinsertできないので、Yesの文字列には先頭からみたときに)より(が大きくなる。

また合計としてもAの方がBより大きくなる。

こういう問題は過去にも出ている (https://atcoder.jp/contests/abc223/tasks/abc223_f) ので これを参考にしつつセグ木で解いた。

#[derive(Debug, Clone, Copy)]
struct M {
    acc: isize,
    mi: isize,
}

impl Monoid for M {
    type S = M;

    fn identity() -> Self::S {
        M { acc: 0, mi: 0 }
    }

    fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {
        M {
            acc: a.acc + b.acc,
            mi: min(a.mi, b.mi + a.acc),
        }
    }
}

fn main() {
    input! {
        n: usize,
        s: Chars,
        q: usize,
    }
    let s = s
        .iter()
        .map(|&e| if e == 'A' { 1 } else { -1 })
        .collect_vec();
    let mut seg = Segtree::<M>::new(n);
    for i in 0..n {
        seg.set(
            i,
            M {
                acc: s[i],
                mi: s[i],
            },
        );
    }
    for _ in 0..q {
        input! {
            t: usize
        }
        if t == 1 {
            input! {
                i: Usize1,
                c: char
            }
            let c = if c == 'A' { 1 } else { -1 };
            seg.set(
                i,
                M {
                    acc: c,
                    mi: c
                }
            );
        } else {
            input! {
                l: Usize1,
                r: Usize1
            }
            let sum = seg.prod(l..=r);
            let mi = sum.mi;
            let sum = sum.acc;
            let ans = if sum >= 0 && mi >= 0 {"Yes"} else {"No"};
            println!("{}", ans);
        }
    }
}