Alternating String の解説

まず、クエリ2について、L=Rのクエリが与えられたならば絶対にYesです。 以下はL < Rの時を考えます。

次のflgを用意します。 v[i] := if i文字目とi+1文字目が等しい {1} else {0}

このようなものが得られた状態を仮定すると、クエリ2はif sum(v[l..r]) == 0 {Yes} else {No} の区間和を計算できればよいです。

クエリ1はL..=R全体を反転しますがv[i]は

• L-1文字とL文字が等しいかのv[L-1]
• R文字とR+1文字が等しいかのv[R]

の2箇所しか変わりません。

よって、ここの1点更新ができればよいわけです。

1点更新、区間取得ができるセグメントツリーを使えばこの問題を解くことができました。

fn main() {
    input! {
        n: usize,
        q: usize,
        s: Chars,
    }
    let mut fen = Segtree::<M>::new(n);
    let mut flg = vec![];
    for i in 0..n - 1 {
        if s[i] == s[i + 1] {
            fen.set(i, 1);
            flg.push(true);
        } else {
            flg.push(false);
        }
    }
    flg.push(false);

    for _ in 0..q {
        input! {
            qq: usize
        }
        if qq == 1 {
            input! {
                l: Usize1,
                r: Usize1
            }
            let di = vec![-1];
            for &di in di.iter() {
                let ni = l as isize + di;
                if ni < 0 || ni >= n as isize {
                    continue;
                }
                let ni = ni as usize;
                if ni + 1 >= n {
                    continue;
                }
                flg[ni] = !flg[ni];
                let num = if flg[ni] {1} else {0};
                fen.set(ni, num);
            }
            let di = vec![0];
            for &di in di.iter() {
                let ni = r as isize + di;
                if ni < 0 || ni >= n as isize {
                    continue;
                }
                let ni = ni as usize;
                if ni + 1 >= n {
                    continue;
                }
                flg[ni] = !flg[ni];
                let num = if flg[ni] {1} else {0};
                fen.set(ni, num);
            }
        } else {
            input! {
                l: Usize1,
                r: Usize1
            }
            if l == r {
                println!("Yes");
                continue;
            }
            let cc = fen.prod(l..r);
            if cc == 0 {
                println!("Yes");
            } else {
                println!("No");
            }
        }
        // println!("{:?}", flg);
    }
}