I - A/AB Insertion 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 525 点

問題文

長さ N の A, B からなる文字列 S が与えられます。
以下のクエリを合計 Q 個処理してください。

1 i c

タイプ 1 : S の i 文字目を c に変更する。

2 l r

タイプ 2 :
文字列 T を、現在の文字列 S の l 文字目から r 文字目までを抜き出した文字列とする。
文字列 T が以下の操作で得られる文字列であれば Yes 、そうでなければ No と出力する。

  • 空文字列から始め、以下の 2 つの操作を好きな順序で 0 回以上何回でも行う。
    • 文字列の(先頭・末尾を含めた)任意の箇所を選択し、そこに A を挿入する。
    • 文字列の(先頭・末尾を含めた)任意の箇所を選択し、そこに AB を挿入する。

制約

  • N は 1 \le N \le 5 \times 10^5 を満たす整数
  • S は A, B からなる長さ N の文字列
  • Q は 1 \le Q \le 2 \times 10^5 を満たす整数
  • 与えられるクエリはタイプ 1,2 のいずれかである
  • タイプ 1 のクエリは以下の制約を満たす
    • i は 1 \le i \le N を満たす整数
    • c は A, B のいずれか
  • タイプ 2 のクエリは以下の制約を満たす
    • l,r は 1 \le l \le r \le N を満たす整数

入力

入力は以下の形式で標準入力から与えられる。

N
S
Q
{\rm Query}_1
{\rm Query}_2
\vdots
{\rm Query}_Q

但し、 {\rm Query}_i は i 個目のクエリを表し、クエリの入力は問題文中の形式に従う。

出力

タイプ 2 のクエリが入力されるごとに、答えを 1 行に出力せよ。

入力例 1

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

出力例 1

Yes
No
Yes
Yes

この入力には 6 個のクエリが含まれます。

  • 最初、 S= AABBAABABB です。
  • 1 つ目のクエリについて、 S の 1 文字目から 10 文字目までを抜き出した T= AABBAABABB は以下の手順を踏むことで得ることができるため、 Yes と出力します。
    • 空文字列から始める。
    • 空文字列の先頭に AB を挿入し、文字列が AB となる。
    • AB の 1 文字目の直後に AB を挿入し、文字列が AABB となる。
    • AABB の末尾に AB を挿入し、文字列が AABBAB となる。
    • AABBAB の 5 文字目の直後に AB を挿入し、文字列が AABBAABB となる。
    • AABBAABB の 7 文字目の直後に AB を挿入し、文字列が AABBAABABB となる。
  • 2 つ目のクエリについて、 S の 5 文字目を B に変更します。その結果、 S= AABBBABABB となります。
  • 3 つ目のクエリについて、 S の 1 文字目から 10 文字目までを抜き出した T= AABBBABABB は問題文中の操作では得られないため、 No と出力します。
  • 4 つ目のクエリについて、 S の 6 文字目から 8 文字目までを抜き出した T= ABA は問題文中の操作で得ることができるため、 Yes と出力します。
  • 5 つ目のクエリについて、 S の 3 文字目を A に変更します。その結果、 S= AAABBABABB となります。
  • 6 つ目のクエリについて、 S の 1 文字目から 10 文字目までを抜き出した T= AAABBABABB は問題文中の操作で得ることができるため、 Yes と出力します。

Score : 525 points

Problem Statement

You are given a string S of length N consisting of A and B.
Process a total of Q queries of the following types.

1 i c

Type 1: Change the i-th character of S to c.

2 l r

Type 2:
Let string T be the string obtained by extracting the l-th through r-th characters of the current string S.
If it is possible to obtain string T by the following operation, output Yes; otherwise, output No.

  • Starting from the empty string, perform the following two operations any number of times, possibly zero, in any order.
    • Choose any position in the string (possibly the beginning or the end) and insert A there.
    • Choose any position in the string (possibly the beginning or the end) and insert AB there.

Constraints

  • N is an integer satisfying 1 \le N \le 5 \times 10^5.
  • S is a string of length N consisting of A and B.
  • Q is an integer satisfying 1 \le Q \le 2 \times 10^5.
  • Each given query is of type 1 or 2.
  • Queries of type 1 satisfy the following constraints:
    • i is an integer satisfying 1 \le i \le N, and
    • c is A or B.
  • Queries of type 2 satisfy the following constraints:
    • l and r are integers satisfying 1 \le l \le r \le N.

Input

The input is given from Standard Input in the following format:

N
S
Q
{\rm Query}_1
{\rm Query}_2
\vdots
{\rm Query}_Q

Here, {\rm Query}_i represents the i-th query, and the input format for a query follows the format described in the problem statement.

Output

Each time a query of type 2 is given, output the answer on one line.

Sample Input 1

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

Sample Output 1

Yes
No
Yes
Yes

This input contains six queries.

  • Initially, S= AABBAABABB.
  • For the 1-st query, T= AABBAABABB, obtained by extracting the 1-st through 10-th characters of S, can be obtained by the following steps, so output Yes.
    • Start from the empty string.
    • Insert AB at the beginning of the empty string, making the string AB.
    • Insert AB right after the 1-st character of AB, making the string AABB.
    • Insert AB at the end of AABB, making the string AABBAB.
    • Insert AB right after the 5-th character of AABBAB, making the string AABBAABB.
    • Insert AB right after the 7-th character of AABBAABB, making the string AABBAABABB.
  • For the 2-nd query, change the 5-th character of S to B. As a result, S= AABBBABABB.
  • For the 3-rd query, T= AABBBABABB, obtained by extracting the 1-st through 10-th characters of S, cannot be obtained by the operation described in the problem statement, so output No.
  • For the 4-th query, T= ABA, obtained by extracting the 6-th through 8-th characters of S, can be obtained by the operation described in the problem statement, so output Yes.
  • For the 5-th query, change the 3-rd character of S to A. As a result, S= AAABBABABB.
  • For the 6-th query, T= AAABBABABB, obtained by extracting the 1-st through 10-th characters of S, can be obtained by the operation described in the problem statement, so output Yes.