Array binaria después de voltear subarrays en un rango dado para consultas Q

Dada una array binaria arr[][] de dimensiones M x N y Q consultas de la forma ( x1, y1, x2, y2) , donde ( x1, y1 ) y ( x2, y2 ) denotan la parte superior izquierda y la parte inferior índices correctos de la subarray requerida para ser volteada (convertir 0s a 1s y viceversa) respectivamente. La tarea es imprimir la array final obtenida después de realizar las consultas Q dadas .

Ejemplos:

Entrada: arr[][] = {{0, 1, 0}, {1, 1, 0}}, consultas[][] = {{1, 1, 2, 3}}
Salida: [[1, 0 , 1], [0, 0, 1]]
Explicación:
La subarray que se volteará es igual a {{0, 1, 0}, {1, 1, 0}} 
La array volteada es {{1, 0, 1 }, {0, 0, 1}}.

Entrada: arr[][] = {{0, 1, 0}, {1, 1, 0}}, consultas[][] = {{1, 1, 2, 3}, {1, 1, 1, 1], {1, 2, 2, 3}}
Salida: [[0, 1, 0], [0, 1, 0]]
Explicación:
Consulta 1:
Subarray a voltear = [[0, 1, 0] , [1, 1, 0]] 
La subarray invertida es [[1, 0, 1], [0, 0, 1]]. 
Por lo tanto, la array modificada es [[1, 0, 1], [0, 0, 1]].
Consulta 2: 
Subarray a voltear = [[1]] 
La subarray volteada es [[0]] 
Por lo tanto, la array es [[0, 0, 1], [0, 0, 1]].
Consulta 3:
Subarray a voltear = [[0, 1], [0, 1]] 
La subarray volteada es [[1, 0], [1, 0]] 
Por lo tanto, la array modificada es [[0, 1, 0 ], [0, 1, 0]].

Enfoque ingenuo: el enfoque más simple para resolver el problema para cada consulta es iterar sobre las subarrays dadas y para cada elemento, verificar si es 0 o 1 y voltear según corresponda. Después de realizar estas operaciones para todas las consultas, imprima la array final obtenida.

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

// C++ program to implement
// the above approach
#include<bits/stdc++.h>
using namespace std;
 
// Function to flip a submatrices
void manipulation(vector<vector<int>> &matrix,
                         vector<int> &q)
{
   
  // Boundaries of the submatrix
  int x1 = q[0], y1 = q[1],
      x2 = q[2], y2 = q[3];
 
  // Iterate over the submatrix
  for(int i = x1 - 1; i < x2; i++)
  {
    for(int j = y1 - 1; j < y2; j++)
    {
       
      // Check for 1 or 0
      // and flip accordingly
      if (matrix[i][j] == 1)
        matrix[i][j] = 0;
      else
        matrix[i][j] = 1;
    }
  }
}
 
// Function to perform the queries
void queries_fxn(vector<vector<int>> &matrix,
                 vector<vector<int>> &queries)
{
  for(auto q : queries)
    manipulation(matrix, q);       
}
 
// Driver code
int main()
{
  vector<vector<int>> matrix = { { 0, 1, 0 },
                                 { 1, 1, 0 } };
  vector<vector<int>> queries = { { 1, 1, 2, 3 },
                                  { 1, 1, 1, 1 },
                                  { 1, 2, 2, 3 } };
   
  // Function call
  queries_fxn(matrix, queries);
  cout << "[";
 
  for(int i = 0; i < matrix.size(); i++)
  {
    cout << "["; 
    for(int j = 0; j < matrix[i].size(); j++)
      cout << matrix[i][j] << " ";
 
    if (i == matrix.size() - 1)
      cout << "]";
    else
      cout << "], ";
  }
   cout << "]";
}
 
// This code is contributed by bgangwar59

// Java program to implement
// the above approach
import java.util.*;
import java.lang.*;
class GFG{
 
// Function to flip a submatrices
static void manipulation(int[][] matrix,
                         int[] q)
{
  // Boundaries of the submatrix
  int x1 = q[0], y1 = q[1],
      x2 = q[2], y2 = q[3];
 
  // Iterate over the submatrix
  for(int i = x1 - 1; i < x2; i++)
  {
    for(int j = y1 - 1; j < y2; j++)
    {
      // Check for 1 or 0
      // and flip accordingly
      if (matrix[i][j] == 1)
        matrix[i][j] = 0;
      else
        matrix[i][j] = 1;
    }
  }
}
 
// Function to perform the queries
static void queries_fxn(int[][] matrix,
                        int[][] queries)
{
  for(int[] q : queries)
    manipulation(matrix, q);       
}
 
// Driver code
public static void main (String[] args)
{
  int[][] matrix = {{0, 1, 0}, {1, 1, 0}};
  int[][] queries = {{1, 1, 2, 3},
                     {1, 1, 1, 1},
                     {1, 2, 2, 3}};
 
  // Function call
  queries_fxn(matrix, queries);
  System.out.print("[");
 
  for(int i = 0; i < matrix.length; i++)
  {
    System.out.print("["); 
    for(int j = 0; j < matrix[i].length; j++)
      System.out.print(matrix[i][j] + " ");
 
    if(i == matrix.length - 1)
      System.out.print("]");
    else
      System.out.print("], ");
  }
  System.out.print("]");
}
}
 
// This code is contributed by offbeat

# Python3 Program to implement
# the above approach
 
# Function to flip a submatrices
def manipulation(matrix, q):
 
    # Boundaries of the submatrix
    x1, y1, x2, y2 = q
 
    # Iterate over the submatrix
    for i in range(x1-1, x2):
        for j in range(y1-1, y2):
 
            # Check for 1 or 0
            # and flip accordingly
            if matrix[i][j]:
                matrix[i][j] = 0
            else:
                matrix[i][j] = 1
 
# Function to perform the queries
def queries_fxn(matrix, queries):
    for q in queries:
        manipulation(matrix, q)
 
 
# Driver Code
matrix = [[0, 1, 0], [1, 1, 0]]
queries = [[1, 1, 2, 3], \
           [1, 1, 1, 1], \
           [1, 2, 2, 3]]
 
# Function call
queries_fxn(matrix, queries)
print(matrix)

// C# program to implement
// the above approach
using System;
 
class GFG{
 
// Function to flip a submatrices
static void manipulation(int[,] matrix,
                         int[] q)
{
     
    // Boundaries of the submatrix
    int x1 = q[0], y1 = q[1],
        x2 = q[2], y2 = q[3];
     
    // Iterate over the submatrix
    for(int i = x1 - 1; i < x2; i++)
    {
        for(int j = y1 - 1; j < y2; j++)
        {
             
            // Check for 1 or 0
            // and flip accordingly
            if (matrix[i, j] == 1)
                matrix[i, j] = 0;
            else
                matrix[i, j] = 1;
        }
    }
}
 
public static int[] GetRow(int[,] matrix, int row)
{
    var rowLength = matrix.GetLength(1);
    var rowVector = new int[rowLength];
     
    for(var i = 0; i < rowLength; i++)
        rowVector[i] = matrix[row, i];
     
    return rowVector;
}
 
// Function to perform the queries
static void queries_fxn(int[,] matrix,
                        int[,] queries)
{
    for(int i = 0; i < queries.GetLength(0); i++)
        manipulation(matrix, GetRow(queries, i));       
}
 
// Driver code
public static void Main(String[] args)
{
    int[,] matrix = { { 0, 1, 0 },
                      { 1, 1, 0 } };
    int[,] queries = { { 1, 1, 2, 3 },
                       { 1, 1, 1, 1 },
                       { 1, 2, 2, 3 } };
     
    // Function call
    queries_fxn(matrix, queries);
    Console.Write("[");
     
    for(int i = 0; i < matrix.GetLength(0); i++)
    {
        Console.Write("["); 
        for(int j = 0; j < matrix.GetLength(1); j++)
            Console.Write(matrix[i, j] + ", ");
         
        if (i == matrix.Length - 1)
            Console.Write("]");
        else
            Console.Write("], ");
    }
    Console.Write("]");
}
}
 
// This code is contributed by Princi Singh

<script>
// Javascript program to implement
// the above approach
 
// Function to flip a submatrices
function manipulation(matrix, q) {
 
    // Boundaries of the submatrix
    let x1 = q[0], y1 = q[1],
        x2 = q[2], y2 = q[3];
 
    // Iterate over the submatrix
    for (let i = x1 - 1; i < x2; i++) {
        for (let j = y1 - 1; j < y2; j++) {
 
            // Check for 1 or 0
            // and flip accordingly
            if (matrix[i][j] == 1)
                matrix[i][j] = 0;
            else
                matrix[i][j] = 1;
        }
    }
}
 
// Function to perform the queries
function queries_fxn(matrix, queries) {
    for (let q of queries)
        manipulation(matrix, q);
}
 
// Driver code
 
let matrix = [[0, 1, 0],
              [1, 1, 0]];
let queries = [[1, 1, 2, 3],
               [1, 1, 1, 1],
               [1, 2, 2, 3]];
 
// Function call
queries_fxn(matrix, queries);
document.write("[");
 
for (let i = 0; i < matrix.length; i++) {
    document.write("[");
    for (let j = 0; j < matrix[i].length; j++) {
        if (j < matrix[i].length - 1) {
            document.write(matrix[i][j] + ", ");
        }
        else {
            document.write(matrix[i][j] + " ");
        }
    }
 
    if (i == matrix.length - 1)
        document.write("]");
    else
        document.write("], ");
}
document.write("]");
 
 
 
// This code is contributed by _saurabh_jaiswal
</script>

[[0, 1, 0], [0, 1, 0]]

Complejidad temporal: O( N * M * Q) 
Espacio auxiliar: O(1)
 

Enfoque eficiente: el enfoque anterior se puede optimizar mediante la programación dinámica y la técnica de suma de prefijos. Marque los límites de las subarrays involucradas en cada consulta y luego calcule la suma del prefijo de las operaciones involucradas en la array y actualice la array en consecuencia. Siga los pasos a continuación para resolver el problema:  

• Inicialice una tabla de espacio de estado 2D dp[][] para almacenar el recuento de cambios en los índices respectivos de la array
• Para cada consulta {x1, y1, x2, y2, K}, actualice la array dp[][] mediante las siguientes operaciones: 
  • pd[x1][y1] += 1
  • pd[x2 + 1][y1] -= 1
  • pd[x2 + 1][y2 + 1] += 1
  • pd[x1][y2 + 1] -= 1
• Ahora, recorra la array dp[][] y actualice dp[i][j] calculando la suma del prefijo de las filas, columnas y diagonales mediante la siguiente relación:

dp[i][j] = dp[i][j] + dp[i-1][j] + dp[i][j – 1] – dp[i – 1][j – 1] 
 

• Si se encuentra que dp[i][j] es impar, reduzca mat[i – 1][j – 1] en 1.
• Finalmente, imprima la array actualizada mat[][] como resultado.

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

import java.util.*;
import java.io.*;
 
// Java program for the above approach
class GFG{
 
  // Function to modify dp[][] array by
  // generating prefix sum
  static void modifyDP(int matrix[][], int dp[][]){
 
    for(int j = 1 ; j <= matrix.length ; j++){
 
      for(int k = 1 ; k <= matrix[0].length ; k++){
 
        // Update the tabular data
        dp[j][k] = dp[j][k] + dp[j-1][k] + dp[j][k-1]- dp[j-1][k-1];
 
        // If the count of flips is even
        if (dp[j][k] % 2 != 0){
          matrix[j-1][k-1] = matrix[j-1][k-1] ^ 1;
        }
      }
    }
  }
 
  // Function to update dp[][] matrix
  // for each query
  static void queries_fxn(int matrix[][], int queries[][], int dp[][]){
    for(int i = 0 ; i < queries.length ; i++){
      int x1 = queries[i][0];
      int y1 = queries[i][1];
      int x2 = queries[i][2];
      int y2 = queries[i][3];
 
      // Update the table
      dp[x1][y1] += 1;
      dp[x2 + 1][y2 + 1] += 1;
      dp[x1][y2 + 1] -= 1;
      dp[x2 + 1][y1] -= 1;
    }
 
    modifyDP(matrix, dp);
  }
 
  // Driver Code
  public static void main(String args[])
  {
    int matrix[][] = new int[][]{
      new int[]{0, 1, 0},
      new int[]{1, 1, 0}
    };
    int queries[][] = new int[][]{
      new int[]{1, 1, 2, 3},
      new int[]{1, 1, 1, 1},
      new int[]{1, 2, 2, 3}
    };
 
    // Initialize dp table
    int dp[][] = new int[matrix.length + 2][matrix[0].length + 2];
 
    queries_fxn(matrix, queries, dp);
    System.out.print("[");
    for(int i = 0 ; i < matrix.length ; i++)
    {
      System.out.print("["); 
      for(int j = 0 ; j < matrix[i].length ; j++){
        System.out.print(matrix[i][j] + " ");
      }
 
      if(i == matrix.length - 1){
        System.out.print("]");
      }else{
        System.out.print("], ");
      }
    }
    System.out.print("]");
  }
}
 
// This code is contributed by entertain2022.

# Python3 program to implement
# the above approach
 
# Function to modify dp[][] array by
# generating prefix sum
def modifyDP(matrix, dp):
     
    for j in range(1, len(matrix)+1):
         
        for k in range(1, len(matrix[0])+1):
             
            # Update the tabular data
            dp[j][k] = dp[j][k] + dp[j-1][k] \
            + dp[j][k-1]-dp[j-1][k-1]
             
            # If the count of flips is even
            if dp[j][k] % 2 != 0:
                matrix[j-1][k-1] = int(matrix[j-1][k-1]) ^ 1
 
# Function to update dp[][] matrix
# for each query
def queries_fxn(matrix, queries, dp):
    for q in queries:
        x1, y1, x2, y2 = q
         
        # Update the table
        dp[x1][y1] += 1
        dp[x2 + 1][y2 + 1] += 1
        dp[x1][y2 + 1] -= 1
        dp[x2 + 1][y1] -= 1
         
    modifyDP(matrix, dp)
 
 
# Driver Code
matrix = [[0, 1, 0], [1, 1, 0]]
queries = [[1, 1, 2, 3], \
           [1, 1, 1, 1], \
           [1, 2, 2, 3]]
 
# Initialize dp table
dp = [[0 for i in range(len(matrix[0])+2)] \
for j in range(len(matrix)+2)]
 
queries_fxn(matrix, queries, dp)
print(matrix)

[[0, 1, 0], [0, 1, 0]]

Complejidad de Tiempo: O(N * M ) 
Espacio Auxiliar: O(N * M)