こう考えた
まずサンプル1を読んでイメージを掴みます。最初の2クエリは次の通りです。
S = abcdcf
T = abccdf
s[1-3] = abc
s[2-6] = bcdcf
この問題はSをソートしたTの部分文字列であるかを判定するため区間がソートされているかを判定しないとなりません。
ソートの判定は後で触れるとして、ソートされていると前提である場合にどのように判定すればいいでしょうか。適当なTを例にとります。
T = aaabbccfffghhhhii
ok1: bbcc
ok2: bccfffghhh
ng1: bccff ghh
ng2: bccfffgghh (★1: ありえない)
ok1のように含まれる文字の種類と文字数が完全にTと一致するパターンが考えられます。
ok2, ng1のようなパターンに注意が必要です。ソートされた文字列Tの部分文字列であるとは、条件1: 部分文字列の最初と最後の文字について、文字数がTの文字数以内でありかつ条件2: それ以外(その間)の文字数が、Tの対応する文字数と一致する必要があることが必要です。
ただし、部分文字列の元の文字列がT自身であったことを考えると条件1のように抜き出した文字の文字数がTの対応する文字の文字数を超えることはないので、条件1は考慮しなくてよいです。例えば、"abbc"だけの文字列からbが3つある"bbb"を抜き出すことは出来ないことから明らかです。このため、ng2(★1)のパターンはありえません。
- 区間の文字列がソートされていることの判定
- 区間の各文字数が高速に得られること
- 各文字数をもとに、最初と最後の文字以外の文字数がTのものと一致すること。つまり、Sと一致すること
- これらの操作について1点更新が可能であること
が出来れば良いことが分かりました。
小問題として、文字列Sの任意の区間がソートされているかを一点更新可能で求めることに注目します。ソートされている文字列sについて$s[i] \leq s[i+1]$ であればよいです。配列orderedを右(i+1)の文字だけ見た時にソートされているか？を示すとし、ソートされている時0、ソートされていない時1とします。この時、ある区間[l,r]がソートされているかを判定するにはordered[l,r-1]の和が0であり、s[l]<=s[r]であればよいです。区間クエリにrは含まなくて良いことに注意します。たとえば、zabcfeaという文字列を考えます。
S = zabcfga
o = 1000011 (ordered)
ok1 abcfg
ok1のようにabcfgのgのindexではorderedが1ですが、これはgの右がaでソートされていないという情報なので、区間がソートされているかの判定には関係ありません。
実装
区間の文字数を数えるには26+1本の区間和、一点更新が可能なデータ構造BITやsegtreeをもちます。26本は各文字(char)に対応し、1本はソートされているか(orderd)に対応します。
更新があるたびにindexについて古い文字の列の値を0にし、新しい文字の列の値を1にします。この操作は$O(logN)$の操作を2回です。次にorderedの更新を行います。この処理は現在の$S$を保持していればindex=iの更新に対して最大で$S[i+1]$のみをみれば判定できて$ordered[i]$を更新するために$O(\log n)$かかります。
クエリはまず区間の各文字の数と、orderedを区間和クエリで求めましょう。これらの操作は$O( \log N)$を27本分繰り返します。各文字数について条件を満たす数量であるかの判定しましょう。
これにより26文字分の定数倍が必要となりますが$O(Q \log N)$で問題を解くことができました。
実装(C++)
int main() {
int n;
cin >> n;
vector<char> dat(n);
vector<int> origcnt(26); // 今のSに何文字含まれているか
vector<fenwick_tree<int>> cnt(26, fenwick_tree<int>(n));
fenwick_tree<int> orderedng(n);
REP(i, n) {
char c;
cin >> c;
c -= 'a';
dat.at(i) = c; // 元の文字S
origcnt.at(c)++; // Sに含まれる各文字数
cnt.at(c).add(i, 1); // BITの更新
}
// 各indexがorderedになっているかの確認
FOR(i, 0, n - 1) if ( (dat.at(i) > dat.at(i + 1))) orderedng.add(i, 1);
int q;
cin >> q;
while (q--) {
int type;
cin >> type;
if (type == 1) {
int ind;
char toc;
cin >> ind >> toc;
ind--;
toc -= 'a';
char fromc = dat.at(ind);
// 各BITの出現位置を直す
cnt.at(fromc).add(ind, -1);
cnt.at(toc).add(ind, 1);
// 各文字の出現回数を修正
origcnt.at(fromc)--;
origcnt.at(toc)++;
// S[ind] を更新
dat.at(ind) = toc;
// orderedかのフラグを更新する。iが更新されたので、i-1, i+1も更新
FOR(i, ind - 1, ind + 2) {
if (i < 0) continue;
if (i > n - 2) continue;
orderedng.add(i, -orderedng.sum(i, i + 1));
if ( (dat.at(i) > dat.at(i + 1))) orderedng.add(i, 1);
}
} else if (type == 2) {
int l, r;
cin >> l >> r;
--l;
--r;
vector<int> tmpcnt(26);
int mival = 100, maval = -1;
REP(i, 26) {
auto xcnt = cnt.at(i).sum(l, r + 1);
tmpcnt.at(i) = xcnt; // 区間に文字iが何回含まれるか？
if (xcnt == 0) continue;
mival = min(mival, i); // 区間に含まれる最小の文字
maval = max(maval, i); // 区間に含まれる最大の文字
}
assert(mival != 100);
assert(maval != -1);
// mival, mavalまで
bool can = true;
// orderedかどうかの判定 (1文字しか含まれていないなら処理をしない)
if (mival != maval) {
auto ord = orderedng.sum(l , r);
if (ord != 0) can = false;
}
// 両端がorderedになっているかの確認。
if (l != r) if (dat.at(l) > dat.at(r)) can = false;
// 区間に含まれる最小と最大の文字が全体の文字数より多い場合創れない
if (tmpcnt.at(mival) > origcnt.at(mival)) can = false;
if (tmpcnt.at(maval) > origcnt.at(maval)) can = false;
// 区間の間の文字は元の文字列の個数と完全に一致しなければならない
FOR(i, mival + 1, maval) {
if (tmpcnt.at(i) != origcnt.at(i)) can = false;
}
if (can) cout << "Yes" << "\n";
else cout << "No" << "\n";
} else {
assert(false);
}
}
}