Максимальное количество нулей между двумя единицами в заданном диапазоне для запросов Q | Сет – 2

Для заданной двоичной строки S размера N и двухмерного массива Q[][] запросов, состоящего из M пар вида {L, R} , задача для каждого запроса состоит в том, чтобы найти максимальное количество нулей , лежащих между двумя единицами в диапазон [L, R] .
Примеры :

Input: S = “1001010”, Q[][] = {{0, 4}, {0, 5}}
Output: 2 3
Explanation: 
The Queries are performed as per the following:

1. Query(0, 4): Print 2 as there are maximum 2 0’s lying between the indices 0 and 3 in the substring over the range [0, 4] i.e., “10010”. 
2. Query(0, 5): Print 3 as there are maximum 3 0’s lying between the indices 0 and 5 in the substring over the range [0, 5] i.e., “100101”.
    

Input: S = “101”, Q[][] = {{0, 2}}
Output: 1

Подход : Другой вариант уже обсуждался в Задаче 1 этой задачи. Отслеживайте два объекта: расположение единиц и количество единиц, которые появились перед любой конкретной позицией. Используйте набор для хранения расположения единиц и массив для хранения ответа. Теперь, чтобы найти ответ в диапазоне [i,j], используйте следующее наблюдение:

Let first and last 1s between given range is located at (i+first) and (i+last), then

Total 0’s between 1’s = total elements between these two locations – total 1’s between these to locations
                                 = location difference between 1’s  – (1’s appeared before (i+last) – 1’s appeared before (i+first) )

Ниже приведена реализация вышеуказанного подхода:

Временная сложность : O(N*logN)
Вспомогательное пространство : O(N)