ARC 071 E - TrBBnsformBBtion

• 問題

問題概要

ABから成る文字列S,Tが与えられる。
次の操作をいくらでも行うことができる。
1. 'AA' -> 'B', 'BB' -> 'A' の変換
2. 'AAA' または 'BBB' の消去

以下のQ個のクエリを処理せよ。
ai,bi,ci,di(1<=i<=Q)が与えられる。
Sの部分文字列S[ai:bi+1]をTの部分文字列[ci:di+1]に一致させることができるか判定せよ。
1<=|S|,|T|<=10⁵,1<=Q<=10⁵,ai<=bi,ci<=di

解法

''(空文字列)<->'AAA'<->'BBB'<->'AB'<->'BA'
'A'<->'BB' 'AA'<->'B'
と相互変換できることに注目する。(ただし''->'AAA'の変換は隣の1文字を用いる)
条件より部分文字列が空文字列であることはないので、部分文字列を何個の'A'に変換できるか、と考えてグループ分けして問題ない。
'A','B'に関してそういう演算子を定義しても問題ないが、
'A'=1,'B'=2として、(文字の和)%3を考えればうまく行くことがわかる。
累積和を計算しておけば各クエリをO(1)で判定できるので十分間に合う。

メモ

変換ができることは考察できたが、''->'AAA'に気づかなくて詰まった。
この難易度ならクエリ系の問題は大体累積和かSeg木を最初に考えて問題なさそう。

コード

#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<utility>
#include<memory>
#include<cmath>
#include<stack>
#include<tuple>
#include<numeric>
#include<cassert>

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back
#define DEBUG false

using namespace std;

using ll = long long;
using P = pair<int,int>;
using Pl = pair<int,ll>;
using Pd = pair<double,double>;
using T = tuple<double,double,int>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60;
const int MAX_N = 100005;
const ll lmod = 1e9+7;

int p[MAX_N],q[MAX_N];

int main(){
  string S,T;
  cin >> S >> T ;
  int temp = 0;
  rep(i,S.size()) p[i+1] = (temp = (temp + int(S[i]-'A') + 1) % 3 );
  temp = 0;
  rep(i,T.size()) q[i+1] = (temp = (temp + int(T[i]-'A') + 1) % 3 );
  int Q,a,b,c,d;
  cin >> Q ;
  rep(i,Q){
    scanf("%d%d%d%d",&a,&b,&c,&d);
    if((p[b]-p[a-1]-q[d]+q[c-1])%3==0) printf("YES\n");
    else printf("NO\n");
  }
  return 0;
}