ABC473 F - A/AB Insertion

A/AB挿入

考え方

まず、切り出した文字列が条件を満たすかを $O(\log N)$ くらいで高速に判定する方法を考える。

条件が言っていることは、各 B に対してそれぞれ自身より前に対応する A を重複なくとれること。
これは、A を $+1$、B を $-1$ として、先頭から任意位置までの累積和が非負であることとも言える。
この判定は、累積和全体に同じ数が足されていても、最小値の話に読み替えれば問題ない。
つまり、対応する区間内にある累積和値の最小値が、先頭の累積和値であることと言い換えられる。

ということで、この累積和の値をクエリ $1$ で動的に変更しながら持てばよい。
必要な操作は、以下の $3$ つ。

ある区間での累積和の最小値を取得する
ある区間の左端の値を取得する
ある区間全体に値を足す

よって、これは遅延segment木で解ける。

クエリ $1$ では、以下を行う。

文字が不変なら、何もしない
B が A になるなら、その位置から後ろすべてに $+2$ する
A が B になるなら、その位置から後ろすべてに $-2$ する

クエリ $2$ では、以下を行う。

先頭の文字の前までの累積和を取得する
先頭の文字の前から末尾の文字の後ろまでの中で、累積和の最小値を取得する
上の $2$ つが一致するなら "Yes"、そうでなければ "No"。

計算量は、$O((N+Q)\log N)$ である。

入力例1での動作

入力を受け取る。

n: 10
s: "AABBAABABB"
q: 6

2 1 10
1 5 B
2 1 10
2 6 8
1 3 A
2 1 10

A を $+1$、B を $-1$ とし、「その位置より左」の累積和を作ると次のようになる。

位置	$0$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$
累積和	$0$	$1$	$2$	$1$	$0$	$1$	$2$	$1$	$2$	$1$	$0$

まず、クエリ 2 1 10 を処理する。

先頭の文字の前の累積和は $0$。
位置 $0$ から $10$ までの累積和の最小値も $0$ なので、一致する。

よって Yes となる。

次に、クエリ 1 5 B を処理する。

$5$ 文字目は A から B に変わる。
そのため、位置 $5$ 以降の累積和すべてに $-2$ する。

位置	$0$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$
累積和	$0$	$1$	$2$	$1$	$0$	$-1$	$0$	$-1$	$0$	$-1$	$-2$

続いて、クエリ 2 1 10 を処理する。

先頭の文字の前の累積和は $0$。
一方、位置 $0$ から $10$ までの累積和の最小値は $-2$ なので、一致しない。

よって No となる。

次に、クエリ 2 6 8 を処理する。

先頭である $6$ 文字目の前、つまり位置 $5$ の累積和は $-1$。
位置 $5$ から $8$ までの累積和は $-1,0,-1,0$ であり、最小値は $-1$ である。

先頭の累積和と一致するので、Yes となる。

続いて、クエリ 1 3 A を処理する。

$3$ 文字目は B から A に変わる。
そのため、位置 $3$ 以降の累積和すべてに $+2$ する。

位置	$0$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$
累積和	$0$	$1$	$2$	$3$	$2$	$1$	$2$	$1$	$2$	$1$	$0$

最後に、クエリ 2 1 10 を処理する。

先頭の文字の前の累積和は $0$。
位置 $0$ から $10$ までの累積和の最小値も $0$ なので、一致する。

よって Yes となる。

注意点

特になし。

別解

特になし。