[ABC285F] Substring of Sorted String 题解

· · 题解

目前题解区唯一一篇未使用树状数组/线段树的题解。

题目大意

给定一个长度为 N 的字符串 S，下标从 1 开始，有以下两种操作：

对于每个操作 2，输出 Yes 或者 No 表示结果。

解题思路

先来考虑 S_{l,l+1,\cdots,r} 什么时候是 T 的子串。设 S_{l,l+1,\cdots,r} 中最大的字符为 Max，最小的字符为 Min，则当且仅当对于所有的满足 Min+1 \leq c \leq Max-1 的字符 c，它在 S_{l,l+1,\cdots,r} 中出现的次数等于它在 T 中出现的次数，且 S_{l,l+1,\cdots,r} 中字符单调不降时，S_{l,l+1,\cdots,r} 是 T 的子串。

于是很多题解开始用树状数组和线段树开始维护，但是实际上我们可以用 set 来维护这个玩意儿。用一个 set 维护所有 s_i<s_{i-1} 的 i，再用 26 个 set 维护每种字符的出现位置。对于每次询问，先找出区间内的最大最小字符，再按照上面说的进行判断即可。代码中有注释。

代码示例

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,q;
string s;
set<int> x,id[30];
signed main(){
    cin>>n>>s>>q;
    s=" "+s;
    for(int i=2;i<s.size();i++) if(s[i]<s[i-1]) x.insert(i);//用于检查区间是否单调不降
    for(int i=1;i<s.size();i++) id[s[i]-'a'].insert(i);
    while(q--){
        int op,l,r;
        char c;
        cin>>op;
        if(op==1){
            cin>>l>>c;
            if(l!=1) if(s[l]<s[l-1]) x.erase(l);
            if(l!=s.size()-1) if(s[l+1]<s[l]) x.erase(l+1);
            id[s[l]-'a'].erase(l);
          //维护修改这一位字符造成的影响
            s[l]=c;//修改
          //维护修改这一位字符造成的影响
            id[s[l]-'a'].insert(l);
            if(l!=s.size()-1) if(s[l+1]<s[l]) x.insert(l+1);
            if(l!=1) if(s[l]<s[l-1]) x.insert(l);
        }else{
            int flg=1;
            cin>>l>>r;
            char Min='z',Max='a';
          //找到区间中出现的最大最小字符
            for(char ck='a';ck<='z';ck++){
                auto it=id[ck-'a'].lower_bound(l);
                if(it!=id[ck-'a'].end()&&*it<=r){
                    if(ck<Min) Min=ck;
                    if(ck>Max) Max=ck;
                }
            }
          //判断其余字符出现次数是否等于总出现次数
          //不等于则答案为 No
            for(char ck=Min+1;ck<=Max-1;ck++){
                if(id[ck-'a'].empty()) continue;
                if((l<=*id[ck-'a'].begin()&&*id[ck-'a'].rbegin()<=r)) continue;
                flg=0;
            }
            auto it=x.upper_bound(l);
            if(it!=x.end()&&*it<=r) flg=0;
          //区间不单调不降则答案为 No
            cout<<(flg?"Yes":"No")<<endl;
        }
    }
    return 0;
}