string - 在多个查询中按字典顺序比较字符串

Question

按字典顺序多次比较字符串形式的两个数字。

我尝试过的

问题很简单，要比较更改后的字符串，但由于多个查询，我收到超出时间限制的错误。

我在互联网上搜索并遇到了线段树来解决范围查询。但遗憾的是，我无法想象它在这里有何帮助。

感谢任何提示。

Answer 1

对于这个问题，线段树似乎有些矫枉过正。 B 什么时候会在字典序上大于 A？在索引 i 处，A[i] = 0，B [i] = 1 且 A[0:i] = B [0:i]。同时遍历两个字符串，并将所有不同的索引保存在一个集合中。

对于索引 i 处的每个查询，将 B 更新为 1。然后检查是否 B[i] = A[i]。如果它们相等，则从索引集中删除 i。否则，将其添加到集合中。如果集合中没有剩余索引，则 A 和 B 现在相等 => 回答是。

如果至少有 1 个元素，则获取最低的索引。如果此索引为 j，则意味着 A[0:j] = B[0:j] 但 A[j] != B[j]。因此，要么 A 为 0，B 为 1，要么 A 为 1，B 为 0。根据情况，回答是或否。

这具有 O(Q log N) 的复杂性，即 Q 的查询量