#include <bits/stdc++.h>
using namespace std;
const int N=1000100;
set<int>s[26];
int n,m,a[N],book[26];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        char c;
        scanf(" %c",&c);
        a[i]=c-'a';
        book[a[i]]++;
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<26;j++){
            if(a[i]==j)continue;
            s[j].insert(i);
        }
    }
    for(int j=0;j<26;j++)s[j].insert(n+1);
    scanf("%d",&m);
    while(m--){
        int opt,x,y;
        char c;
        scanf("%d",&opt);
        if(opt==1){
            scanf("%d %c",&x,&c);
            y=c-'a';
            s[a[x]].insert(x);
            s[y].erase(x);
            book[a[x]]--;
            book[y]++;
            a[x]=y;
        }
        else{
            scanf("%d%d",&x,&y);
            int flag=1,flag2=1,t=a[x];
            while(x<=y){
if(t>=26){flag=0;break;}
                set<int>::iterator it=s[t].lower_bound(x);
                int cnt=*it-x;
                if(!flag2&&*it<=y&&cnt!=book[t]){flag=0;break;}
                x=*it;
                flag2=0;
                t++;
            }
            if(flag)puts("Yes");
            else puts("No");
        }
    }
    return 0;
}

即将推出新的做法，敬请期待

一道比较简单好想的数据结构题。

我们不妨先分析 $T$ 串的性质，由题意得 $T$ 的字母是递增的，那意味着我询问的子串也应该递增的。

但是子串递增并不意味着他是 $T$ 的子串，因为排序后可能会有其他的字母插入进来。举个例子：

$$\begin{aligned} S=\tt{aaaaaabbbbddyyyyzzzffbaaaz}\\ T=\tt{aaaaaaaaabbbbbddffyyyyzzzz} \end{aligned}$$

假设我们现在查询 $\tt{aabbbbddyy}$ 这个子串是否是 $T$ 的一个子串。

我们不难发现将 $S$ 串排序后发生了以下几个事情：

1. $\tt a$ 和 $\tt z$ 被归位了，看上去并不影响我们的查询。
2. $\tt b$ 被塞了一个进去。
3. $\tt f$ 被塞了两个进去，但是我们原本的子串并没有 $\tt f$。

所以经过简单的分析，我们得到如下结论：

1. 在 $S_l+1$ 到 $S_r-1$ 的所有字母中，其在子串中的出现次数应当等于全串的出现次数。
2. 跟 $S_l$ 和 $S_r$ 相同的字母不影响查询。
3. 区间要递增。

看上去 “区间递增” 是最好做的，不妨想一下如何用数据结构维护。

• 如果 $S_i\geqslant S_{i-1}$，那么我们令 $a_i=1$，否则 $a_i=-1$。

那么一个区间 $[l,r]$ 递增的条件可以转化为 $\sum\limits_{l+1}^r a_i=r-l$。开一个线段树维护即可，每次询问都要检查如上条件，修改时考虑新的字符与其前后的关系，要更改两处线段树的值。

“出现次数” 这个条件就十分简单了，不难发现值域只有 $26$，可以考虑开 $26$ 个线段树或者树状数组。每一个线段树/树状数组维护一个值，如果串中 $S_i=p$，那么 $tr_{p,i}=1$，累加起来即可得到出现次数。