Picking Strings
题意翻译
给定两个由$A$,$B$,$C$组成的字符串$S$和$T$,存在四种对字符串子串(连续)的变换法则:
1. $f_1(A)=BC$
2. $f_2(B)=AC$
3. $f_3(C)=AB$
4. $f_4(AAA)=\varnothing$(空串)
现在有$n$个询问,每个询问由$a,b,c,d$组成,表示询问是否能够通过若干次变换将子区间为$[a,b]$的$S$串变换为子区间为$[c,d]$的$T$串。
题目描述
Alice has a string consisting of characters 'A', 'B' and 'C'. Bob can use the following transitions on any substring of our string in any order any number of times:
- A ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF923D/5a518872d8942914aef6c33d251688a64a8d6d74.png)BC
- B ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF923D/5a518872d8942914aef6c33d251688a64a8d6d74.png)AC
- C ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF923D/5a518872d8942914aef6c33d251688a64a8d6d74.png)AB
- AAA ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF923D/5a518872d8942914aef6c33d251688a64a8d6d74.png) empty string
Note that a substring is one or more consecutive characters. For given queries, determine whether it is possible to obtain the target string from source.
输入输出格式
输入格式
The first line contains a string $ S $ ( $ 1<=|S|<=10^{5} $ ). The second line contains a string $ T $ ( $ 1<=|T|<=10^{5} $ ), each of these strings consists only of uppercase English letters 'A', 'B' and 'C'.
The third line contains the number of queries $ Q $ ( $ 1<=Q<=10^{5} $ ).
The following $ Q $ lines describe queries. The $ i $ -th of these lines contains four space separated integers $ a_{i} $ , $ b_{i} $ , $ c_{i} $ , $ d_{i} $ . These represent the $ i $ -th query: is it possible to create $ T[c_{i}..d_{i}] $ from $ S[a_{i}..b_{i}] $ by applying the above transitions finite amount of times?
Here, $ U[x..y] $ is a substring of $ U $ that begins at index $ x $ (indexed from 1) and ends at index $ y $ . In particular, $ U[1..|U|] $ is the whole string $ U $ .
It is guaranteed that $ 1<=a<=b<=|S| $ and $ 1<=c<=d<=|T| $ .
输出格式
Print a string of $ Q $ characters, where the $ i $ -th character is '1' if the answer to the $ i $ -th query is positive, and '0' otherwise.
输入输出样例
输入样例 #1
AABCCBAAB
ABCB
5
1 3 1 2
2 2 2 4
7 9 1 1
3 4 2 3
4 5 1 3
输出样例 #1
10011
说明
In the first query we can achieve the result, for instance, by using transitions ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF923D/bc389404fee8abb9f1186ea5ef11a96a445486ca.png).
The third query asks for changing AAB to A — but in this case we are not able to get rid of the character 'B'.