问题分析

本题是一道关于字符串字符范围判定的问题，核心任务是判断每个字符串是否为"特殊字符串"。一个字符串被定义为特殊字符串的条件是：该字符串移除后，剩余所有字符串的最大字符（按a-z顺序）均大于该字符串的最小字符。

算法思路

1. 预处理每个字符串的特征值

对于每个字符串，计算两个关键值：

• maxx[i]：第i个字符串中最大字符对应的数值（a为$0$，b为$1$，…，z为$25$），即：$$\text{maxx}[i] = \max\{ c - 'a' \mid c \in \text{第}i\text{个字符串} \} $$
• minn[i]：第i个字符串中最小字符对应的数值，即：$$\text{minn}[i] = \min\{ c - 'a' \mid c \in \text{第}i\text{个字符串} \} $$

2. 利用多重集合维护最大字符集

• 使用multiset<ll> s存储所有字符串的maxx值，便于高效查询和修改。
• 对于每个字符串i，执行以下操作：
  1. 从集合s中临时移除maxx[i]（模拟"移除第i个字符串"的场景）。
  2. 检查剩余集合s的最小元素（即s.begin()指向的元素）：
     • 若集合为空（仅剩当前字符串），或剩余集合的最小元素> minn[i]，则该字符串是特殊字符串，输出1。
     • 否则，输出0。
  3. 将maxx[i]重新插入集合s，恢复集合状态以处理下一个字符串。

关键复杂度分析

• 预处理阶段：计算每个字符串的maxx和minn，每个字符串需遍历其所有字符，总时间复杂度为$O(\sum \text{len}(x_i))$，其中$\text{len}(x_i)$是第i个字符串的长度。
• 判定阶段：
  • 对于每个字符串，集合的erase和insert操作复杂度为$O(\log n)$（multiset的平衡树实现）。
  • 查询集合最小元素的复杂度为$O(1)$。
  • 总时间复杂度为$O(n \log n)$，其中$n$是字符串的数量。

代码解析

算法的核心是利用multiset高效维护和查询最大字符集，通过临时移除-检查-恢复的流程，在$O(n \log n)$时间内完成所有字符串的判定，简洁且高效。