Recuento máximo de 0 entre dos 1 en un rango determinado para consultas Q | Juego – 2

Dada una string binaria S de tamaño N y una array 2D Q[][] de consultas que consta de M pares de la forma {L, R} , la tarea para cada consulta es encontrar el número máximo de 0 que se encuentran entre dos 1 en el rango [L, R] .
Ejemplos :

Entrada: S = “1001010”, Q[][] = {{0, 4}, {0, 5}}
Salida: 2 3
Explicación: 
Las consultas se realizan de la siguiente manera:

1. Consulta (0, 4): Imprima 2 ya que hay un máximo de 2 0 entre los índices 0 y 3 en la substring sobre el rango [0, 4], es decir, «10010». 
2. Consulta (0, 5): Imprima 3 ya que hay un máximo de 3 0 entre los índices 0 y 5 en la substring sobre el rango [0, 5], es decir, «100101».
    

Entrada: S = “101”, Q[][] = {{0, 2}}
Salida: 1

Enfoque : Otra variación ya se discute en el Conjunto 1 de este problema. Realice un seguimiento de dos entidades: la ubicación de los 1 y el número de 1 que apareció antes de cualquier posición específica. Use un conjunto para almacenar la ubicación de los 1 y una array para almacenar la respuesta. Ahora, para encontrar la respuesta en el rango [i, j], use la siguiente observación:

Deje que el primer y el último 1 entre el rango dado se encuentre en (i+primero) y (i+último), luego

Total de 0 entre 1 = elementos totales entre estas dos ubicaciones – total de 1 entre estas y ubicaciones
                                 = diferencia de ubicación entre 1 – (1 apareció antes (i+último) – 1 apareció antes (i+primero))

A continuación se muestra la implementación del enfoque anterior:

// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to get the number of
// 0s between two 1s
vector<int>
zBetweeno(string s,
          vector<vector<int> >& queries)
{
    // Store location of 1s
    set<int> ones;
 
    // Store number of candles before i
    vector<int> one(s.size(), 0);
 
    // Store result
    vector<int> res;
 
    // Storing number of candles before
    // a specific position
    // and locations of candles in a set
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '1') {
            ones.insert(i);
            one[i]++;
        }
        if (i != 0)
            one[i] += one[i - 1];
    }
 
    // Iterating over queries
    for (auto&& query : queries) {
 
        // Get the location of first 1
        int ss
            = *ones.lower_bound(query[0]);
 
        // Get the location of last 1
        int ee
            = s[query[1]] == '1'
                  ? query[1]
                  : *--ones.lower_bound(query[1]);
 
        // Check for corner cases
        if (ss > query[1]
            || ee < query[0]) {
            res.push_back(0);
            continue;
        }
 
        int tot
            = one[ee] - one[ss];
        int loc = ee - ss;
 
        // Storing result of the query
        res.push_back(loc
                      - tot);
    }
 
    return res;
}
 
// Driver code
int main()
{
    vector<vector<int> > queries
      = { { 0, 4 }, { 0, 5 } };
    string input = "1001010";
 
    vector<int> res =
      zBetweeno(input, queries);
 
    for (auto elem : res)
        cout << elem << " ";
    cout << endl;
}

import java.util.*;
import java.io.*;
 
// Java program for the above approach
class GFG{
 
  // Function to get the number of
  // 0s between two 1s
  public static ArrayList<Integer> zBetweeno(String s, ArrayList<ArrayList<Integer>> queries)
  {
    // Store location of 1s
    TreeSet<Integer> ones = new TreeSet<Integer>();
 
    // Store number of candles before i
    int one[] = new int[s.length()];
 
    // Store result
    ArrayList<Integer> res = new ArrayList<Integer>();
 
    // Storing number of candles before
    // a specific position
    // and locations of candles in a set
    for (int i = 0 ; i < s.length() ; i++) {
      if (s.charAt(i) == '1') {
        ones.add(i);
        one[i]++;
      }
      if (i != 0){
        one[i] += one[i - 1];
      }
    }
 
    // Iterating over queries
    for (int i = 0 ; i < queries.size() ; i++) {
      ArrayList<Integer> query = queries.get(i);
       
      // Get the location of first 1
      int ss = ones.ceiling(query.get(0));
 
      // Get the location of last 1
      int ee = s.charAt(query.get(1)) == '1' ? query.get(1) : ones.floor(query.get(1)-1);
 
      // Check for corner cases
      if (ss > query.get(1) || ee < query.get(0)) {
        res.add(0);
        continue;
      }
 
      int tot = one[ee] - one[ss];
      int loc = ee - ss;
 
      // Storing result of the query
      res.add(loc - tot);
    }
 
    return res;
  }
 
  // Driver code
  public static void main(String args[])
  {
    ArrayList<ArrayList<Integer> > queries = new ArrayList<>(
      List.of(
        new ArrayList<Integer>(
          List.of(0, 4)
        ),
        new ArrayList<Integer>(
          List.of(0, 5)
        )
      )
    );
 
    String input = "1001010";
 
    ArrayList<Integer> res = zBetweeno(input, queries);
 
    for(int i = 0 ; i < res.size() ; i++){
      System.out.print(res.get(i) + " ");
    }
    System.out.println("");
  }
}
 
// This code is contributed by subhamgoyal2014.

# Python 3 implementation of the above approach
from bisect import bisect_left
 
# Function to get the number of
# 0s between two 1s
def zBetweeno(s, queries):
 
    # Store location of 1s
    ones = set([])
 
    # Store number of candles before i
    one = [0]*len(s)
 
    # Store result
    res = []
 
    # Storing number of candles before
    # a specific position
    # and locations of candles in a set
    for i in range(len(s)):
        if (s[i] == '1'):
            ones.add(i)
            one[i] += 1
 
        if (i != 0):
            one[i] += one[i - 1]
 
    # Iterating over queries
    for query in queries:
 
        # Get the location of first 1
        ss = bisect_left(list(ones), query[0])
 
        # Get the location of last 1
        if s[query[1]] == '1':
            ee = query[1]
        else:
            ee = bisect_left(list(ones), query[1])
 
        # Check for corner cases
        if (ss > query[1]
                or ee < query[0]):
            res.append(0)
            continue
 
        tot = one[ee] - one[ss]
        loc = ee - ss
 
        # Storing result of the query
        res.append(loc
                   - tot)
    return res
 
# Driver code
if __name__ == "__main__":
 
    queries = [[0, 4], [0, 5]]
    input = "1001010"
 
    res = zBetweeno(input, queries)
 
    for elem in res:
        print(elem, end=" ")
 
        # This code is contributed by ukasp.

2 3 

Complejidad de tiempo : O(N*logN)
Espacio auxiliar : O(N)