string - 字符串上的回文运算

Question

最初给你一个字符串 S 和一些 Q 查询。对于每个查询，您将有 2 个整数 L 和 R。对于每个查询，您必须执行以下操作：

排列从 L 到 R 的字母，组成一个回文。如果你能形成许多这样的回文，那么取一个字典序最少的。如果在重新排列字母时不可能出现回文，则忽略该查询。

您必须在所有查询之后找到最终字符串。

约束：

• 1 <= 长度(S) <= 10^5

• 1 <= Q <= 10^5

• 1<= L <= R <= 长度（S）

样本输入：

4

MMCS 1

1 3

样本输出：

mcms

解释： 初始字符串是 mmcs，有 1 个查询要求从 1 3 生成回文，所以回文将是 mcm。因此字符串将 mcms。

如果每个查询花费 O(N) 时间，则总时间复杂度将为 O(NQ)，这将给出 TLE。所以每个查询应该花费大约 O(logn) 时间。但是我想不出任何可以解决这个问题的方法。我认为既然我们只需要找到最终的字符串而不是每个查询结果的内容，我想肯定有其他方法可以解决这个问题。有谁能够帮我？

标签： stringpalindrome