贪心、字符串

判断是否符合要求的子序列不能找到，考虑贪心，由于每个位的可选范围固定，当前位越晚匹配，留有的余地就越小，整个子序列越不可能匹配成功。

对于子序列的每个位找最晚出现的字符，注意是找不同字符中下一次出现最晚的那个，也就是说对于 mondzd 这种字符串来说找到的应该是 z 而不是 d，这样才是对的。注意处理没找到目标字符的情况。

单组数据时间复杂度 $O(|s| \log |s|)$。

#include<bits/stdc++.h>
using namespace std;
int n,m,pos;
inline void ex(string &x){x.insert(x.begin(),'#');}
void solution(){
    set<int> w[30];
    string s,l,r;
    cin>>s>>m>>l>>r,pos=0,n=s.size();
    ex(s),ex(l),ex(r);
    for(int i=1;i<=n;i++) w[s[i]-'0'].emplace(i);
    for(int i=0;i<=9;i++) w[i].emplace(n+1);
    for(int i=1;i<=m;i++){
        int nxt=pos;
        for(int j=l[i];j<=r[i];j++) nxt=max(nxt,*w[j-'0'].upper_bound(pos));
        if(nxt==n+1) return puts("YES"),void();
        pos=nxt;
    }
    puts("NO");
}
int T;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--) solution();
    return 0;
}