сравнивать строки лексикографически в нескольких запросах - PullRequest
Новая
       13

сравнивать строки лексикографически в нескольких запросах

0 голосов
/ 05 мая 2018

Сравните два числа в виде строки лексикографически несколько раз.

Что я пробовал

Вопрос прост: сравнить строку после изменения, но я получаю сообщение об ошибке превышения лимита времени из-за нескольких запросов.

Я искал в интернете и наткнулся на дерево сегментов для решения запросов диапазона. Но, увы, я не могу представить, как это может помочь.

Любая подсказка приветствуется.

1 Ответ

0 голосов
/ 05 мая 2018

Сегментное дерево кажется излишним для этой проблемы. Когда В будет лексикографически больше А? Когда по индексу i, A [i] = 0, B [i] = 1 и A [0: i] = B [0: i]. Перебирайте обе строки одновременно и сохраняйте все индексы, где они разные.

Для каждого запроса по индексу i обновите B до 1. Затем проверьте, если B [i] = A [i]. Если они равны, удалите i из набора индексов. В противном случае добавьте его в набор. Если в наборе не осталось индексов, A и B теперь равны => ответить YES.

Если есть хотя бы 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 количество запросов

...