\(\def \set #1#2{\{ #1 \ \vert \ #2 \}}\)
解法
\(S,T\) の持つべき性質を調べる． \(S_{l,r} := S_{[l,r)}\) とおく． 文字列 \(U\) と \(a \in \Sigma := Alphabet\) に対して， \(cnt_{U}(a)\) を，文字列 \(U\) に現れる \(a\) の個数とする． すなわち， \(cnt_{U}(a) := \#\set{i \in Dom(U)}{ U_{i} = a }\) とする．
- \(S_{l,r}\) はソートされている必要がある．
- (\(S_{l,r}\) はソートされていると仮定して) for any \(c \in (S_{l}, S_{r-1})\) such that \(cnt_{S_{l,r}}(c) = cnt_{T}(c)\).
前者は， 隣同士だけ比べれば十分． 後者は， 任意の \(c \in \Sigma\) に対して \(cnt_{T}(c) = cnt{S}(c)\) が成り立つので， \(S\) だけで判定できる．
実装
後者は，segtree を \(\# \Sigma = 26\) 個持てば良い． 更新クエリは，順序は前後しか変わらないし，cnt も 1箇所だけ更新すれば十分．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
ll op(ll a, ll b){ return a+b; }
ll e() { return 0; }
int main() {
ll n;
cin >> n;
string s; cin >> s;
ll q; cin >> q;
rep(i,n) s[i] -= 'a';
using T = segtree<ll,op,e>;
T t_ord(n-1);
auto add_seg = [&](T &t, ll p, ll x){
t.set(p, t.get(p) + x);
};
auto add_query = [&](ll p, ll x){
add_seg(s_cnt[s[p]], p, x); // s_cnt[s[p]]
if(p < n-1 && s[p] > s[p+1]) add_seg(t_ord, p, x);
if(p-1 >= 0 && s[p-1] > s[p]) add_seg(t_ord, p-1, x); // コピペミス: p-1
};
rep(i,n) add_seg(s_cnt[s[i]], i, 1);
rep(i,n-1) add_seg(t_ord, i, s[i] > s[i+1]);
rep(qi,q){
ll ty; cin >> ty;
if(ty == 1){
ll p; char c; cin >> p >> c;
--p;
c -= 'a'; // rem -= 'a'
add_query(p,-1);
s[p] = c;
add_query(p,+1);
} else{
ll l,r; cin >> l >> r;
--l;
char cl = s[l];
char cr = s[r-1];
bool ok = true;
srep(c,cl+1,cr){
ok &= s_cnt[c].prod(l,r) == s_cnt[c].all_prod(); // all_prod を使えば，全体の個数は保持する必要が無い．
}
ok &= t_ord.prod(l,r-1) == 0;
if(ok) cout << "Yes\n";
else cout << "No\n";
}
}
return 0;
}
