Original proposer: physics0523

Interpret A as \(+1\), and B as \(-1\).

No matter how you insert AB or A, no prefix sum becomes negative.
Conversely, if no prefix sum is negative, the desired string can always be constructed.
Proof:
Consider repeatedly removing AB until the string contains no B.
By the assumption that no prefix sum is negative, the prefix sum up to the position right before the first occurrence of B is always positive. Therefore, there is always an A right before that B. Removing the AB does not affect the other prefix sums (because the removed elements sum to \(0\)), so it remains that no prefix sum is negative.
Finally, by inverting the timeline and rewording removals to insertions, we can assert that the desired string can be obtained indeed.

All that left is, given a substring, to determine if any prefix sum is negative.
One way is to use a segment tree with lazy propagation. Specifically, it suffices to support segment addition and segment minimum-value retrieval to maintain the cumulative sums at each point.

The time complexity of this solution is \(O(N + Q \log N)\).

Sample code (C++):

#include<bits/stdc++.h>
#include<atcoder/all>

using namespace std;
using namespace atcoder;

using S=int;
using F=int;

S op(S l,S r){return min(l,r);}
S e(){return 1e9;}
S mapping(F l,S r){return (l+r);}
F composition(F l,F r){return (l+r);}
F id(){return 0;}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  string s;
  cin >> n >> s;
  vector<S> ini(n+1,0);
  for(int i=0;i<n;i++){
    if(s[i]=='A'){ini[i+1]=ini[i]+1;}
    else{ini[i+1]=ini[i]-1;}
  }
  lazy_segtree<S,op,e,F,mapping,composition,id> seg(ini);
  int q;
  cin >> q;
  while(q--){
    int typ;
    cin >> typ;
    if(typ==1){
      int i;
      string c;
      cin >> i >> c;
      i--;
      int del;
      if(s[i]=='A'){del=-1;}
      else{del=1;}
      s[i]=c[0];
      if(s[i]=='A'){del++;}
      else{del--;}
      seg.apply(i+1,n+1,del);
    }
    else{
      int l,r;
      cin >> l >> r;
      l--;
      if(seg.prod(l,r+1)==seg.get(l)){cout << "Yes\n";}
      else{cout << "No\n";}
    }
  }
  return 0;
}