// compile: g++ -o data data.cpp -O3 -std=gnu++20 -Wall -Wextra -Wshadow -D_GLIBCXX_ASSERTIONS -ggdb3 -fmax-errors=2 -DLOCAL
// run: ./data < data.in
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#ifdef LOCAL
#include <debug/codeforces.h>
#define debug(x...) {_variables(#x);_print(x);}
#define deb(x...) {_print(x);}
#else
#define debug(x...)
#define deb(x...)
#endif
template<typename...Args> void print_(Args...args){((cout<<args<<" "),...)<<endl;}
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define sz(v) ((int)(v).size())
#define print(...) print_(__VA_ARGS__);
#define INTINF (int)(9223372036854775807)
#define int long long
#define MAXN 200010
struct node {
struct node *ch[2];
struct node *p;
int ind, letter, cnt[26];
int lm, rm;
bool ordered;
};
node *root = nullptr;
node datalist[MAXN];
int cnt = 0;
int n, q, total[26];
struct node *newnode(int ind, int letter) {
node *x = datalist + ind;
x->p = x->ch[0] = x->ch[1] = nullptr;
x->ind = ind;
memset(x->cnt, 0, sizeof(x->cnt));
x->cnt[letter] = 1;
x->ordered = 1;
x->lm = x->rm = x->letter = letter;
return x;
}
int get(struct node *x) {
return (x->p->ch[1] == x);
}
void maintain(struct node *x) {
if (!x) return;
if (!x->ch[0] && !x->ch[1]) {
x->ordered = 1;
x->lm = x->rm = x->letter;
memset(x->cnt, 0, sizeof(x->cnt));
x->cnt[x->letter] = 1;
}
else if (!x->ch[0]) {
x->ordered = x->ch[1]->ordered && (x->letter <= x->ch[1]->lm);
x->lm = x->letter;
x->rm = x->ch[1]->rm;
for (int i = 0; i < 26; ++i) x->cnt[i] = x->ch[1]->cnt[i];
++x->cnt[x->letter];
}
else if (!x->ch[1]) {
x->ordered = x->ch[0]->ordered && (x->letter >= x->ch[0]->rm);
x->lm = x->ch[0]->lm;
x->rm = x->letter;
for (int i = 0; i < 26; ++i) x->cnt[i] = x->ch[0]->cnt[i];
++x->cnt[x->letter];
}
else {
x->ordered = x->ch[0]->ordered && x->ch[1]->ordered && (x->letter >= x->ch[0]->rm) && (x->letter <= x->ch[1]->lm);
x->lm = x->ch[0]->lm;
x->rm = x->ch[1]->rm;
for (int i = 0; i < 26; ++i) x->cnt[i] = x->ch[0]->cnt[i] + x->ch[1]->cnt[i];
++x->cnt[x->letter];
}
}
void rotate(struct node *x) {
node *y = x->p;
node *z = y->p;
int t = get(x);
y->ch[t] = x->ch[t ^ 1];
if (x->ch[t ^ 1]) x->ch[t ^ 1]->p = y;
x->ch[t ^ 1] = y;
y->p= x;
if (z) z->ch[y == z->ch[1]] = x;
x->p= z;
maintain(y);
maintain(x);
}
void splay(struct node *x, struct node *target) {
for (struct node *f; f = x->p, f != target; rotate(x)) {
if (f->p!= target) rotate((get(x) == get(f)) ? f : x);
}
if (target == NULL) root = x;
}
void insert(int ind, int letter) {
if (!root) {
root = newnode(ind, letter);
return;
}
struct node *x = root;
for (; ; x = x->ch[ind > x->ind]) {
if (x->ind == ind) {
maintain(x);
maintain(x->p);
splay(x, NULL);
return;
}
if (!x->ch[ind > x->ind]) {
x->ch[ind > x->ind] = newnode(ind, letter);
x->ch[ind > x->ind]->p = x;
maintain(x);
splay(x->ch[ind > x->ind], nullptr);
return;
}
}
}
void treavel(struct node *x) {
if (x) {
treavel(x->ch[0]);
// deb(x->ind, x->letter, x->ordered, x->ch[0] ? x->ch[0]->ind : -1, x->ch[1] ? x->ch[1]->ind : -1);
// deb(x->ind, x->cnt[0], x->cnt[1], x->cnt[2], x->cnt[3], x->cnt[4], x->cnt[5])
treavel(x->ch[1]);
}
}
string check(node *x) {
if (!x->ordered) return "No";
int s = 0, t = 25;
while (!x->cnt[s]) ++s;
while (!x->cnt[t]) --t;
++s, --t;
for (int i = s; i <= t; ++i) if (x->cnt[i] != total[i]) return "No";
return "Yes";
}
int32_t main() {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
cin >> n; string s; cin >> s;
insert(0, 0); insert(n + 1, 0);
for (int i = 0; i < (int)s.length(); ++i) {
insert(i + 1, s[i] - 'a');
++total[s[i] - 'a'];
}
cin >> q;
while (q--) {
int op; cin >> op;
if (op == 1) {
int x; char ch; cin >> x >> ch;
--total[(datalist + x)->letter];
++total[ch - 'a'];
splay(datalist + x, nullptr);
root->letter = ch - 'a';
maintain(root);
}
else {
int l, r; cin >> l >> r;
splay(datalist + l - 1, nullptr);
splay(datalist + r + 1, root);
cout << check(root->ch[1]->ch[0]) << endl;
}
}
return 0;
}
No Comments