题解

思路推导

对一个固定密码，判断它是否为 $s$ 的子序列时，总可以贪心选择每个数字在当前位置之后的最早出现位置。现在要在每一位的允许数字中寻找一个无法匹配的密码。

处理密码第 $i$ 位时，若某个允许数字在当前位置之后不存在，立刻可以选择它构成失败前缀，答案为 YES。否则，为了让后续最难继续匹配，应把当前位置推进到所有允许数字的下一出现位置中最晚的一个。

做法

预处理字符串 $s$ 从每个位置向后看，数字 $0$ 到 $9$ 的下一出现位置。初始位置在字符串之前。

依次处理密码各位，枚举 $l_i$ 到 $r_i$ 的数字。若某个数字没有下一出现位置，输出 YES；否则令当前位置等于这些下一出现位置的最大值。若 $m$ 位都能处理完，输出 NO。

正确性证明

归纳证明：处理完前 $i$ 位后，算法维护的位置等于所有允许长度为 $i$ 的密码前缀在采用最早匹配时能到达的最晚位置。

第 $i+1$ 位若存在某个允许数字没有下一出现位置，则取到当前最晚前缀并追加该数字即可得到非子序列密码。否则，每个允许数字都能从当前状态转移；任何其他前缀的位置不晚于当前状态，其相同数字的最早匹配位置也不会更晚。因此，枚举当前状态的全部允许数字并取最晚者，恰得到下一层所有前缀的最晚位置，归纳成立。

若全过程没有缺失转移，则每个允许密码都能完成匹配，不存在强密码；若中途失败，构造出的前缀任意补全后仍不是子序列。故判定正确。

复杂度分析

预处理时间为 $O(10|s|)$，处理每组范围的时间为 $O(10m)$，空间复杂度为 $O(10|s|)$。