ABC341 E - Alternating String

atcoder.jp

問題

• 0と1で作られた文字列があるよ
• 0と1が交互に出てくる文字列を良い文字列と呼ぶよ
• 以下のクエリを処理してね！
  • 1：L文字目からR文字目までの0と1を反転させてね！
  • 2：L文字目からR文字目までをそのまま抜き出した時、その文字列は良い文字列になってる？

成約

• $1 \leq N,Q \leq 5 \times10^{5}$

思考

• 先週の遅延セグ木もあったし、「区間を一気に反転…遅延セグ木…！？」と思ってこねこねしてたけど遅延セグ木じゃなかった…
• Tips：区間反転は、区間の左右を意識しようね
• L~Rの中は、01反転したところで、良い文字列なら良い文字列のまま。悪い文字列なら悪い文字列のままなので。

コード

from atcoder.segtree import SegTree

N,Q = map(int,input().split())
S = input()

seg = SegTree(max, 0, N)

for i in range(N-1):
    if S[i] == S[i+1]:
        seg.set(i, 1)

for _ in range(Q):
    q,L,R = map(int,input().split())
    L-=1
    R-=1
    
    if q == 1:
        if L != 0:
            seg.set(L-1, seg.get(L-1)^1)
        if R != N-1:
            seg.set(R, seg.get(R)^1)
    else:
        if seg.prod(L,R) == 0:
            print('Yes')
        else:
            print('No')