Dada una array arr[] que consiste en N 0 s ( indexación basada en 1 ) y otra array query[] , con cada fila de la forma {L, R} , la tarea para cada consulta (L, R) es agregar una valor de (i – L + 1) sobre el rango [L, R] e imprima la array arr[] obtenida después de realizar todas las consultas.
Ejemplos:
Entrada: arr[] = {0, 0, 0}, query[][] = {{1, 3}, {2, 3}}
Salida: 1 3 5
Explicación: Inicialmente, la array es {0, 0, 0 }.
Consulta 1: Rango de índices involucrados: [1, 3]. El valor (i – 1 + 1) para cada índice i en el rango es {1, 2, 3}. Agregar estos valores modifica la array a {1, 2, 3}.
Consulta 2: Rango de índices involucrados: [2, 3]. El valor (i – 2 + 1) para cada índice i en el rango es {0, 1, 2}. Agregar estos valores modifica la array a {1, 3, 5}.
Por lo tanto, la array modificada es {1, 3, 5}.Entrada: arr[] = {0, 0, 0, 0, 0, 0, 0}, consulta[][] = {{1, 7}, {3, 6}, {4, 5}}
Salida: 1 2 4 7 10 10 7
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es atravesar la array dada sobre el rango [L, R] y agregar el valor (i – L + 1) a cada elemento en el rango para cada consulta. Después de completar todas las consultas, imprima la array modificada obtenida arr[] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to perform the given queries
// in the given empty array of size N
void updateQuery(vector<vector<int> > queries,
int N)
{
// Initialize an array a[]
vector<int> a(N + 1, 0);
// Stores the size of the array
int n = N + 1;
int q = queries.size();
// Traverse the queries
for (int i = 0; i < q; i++) {
// Starting index
int l = queries[i][0];
// Ending index
int r = queries[i][1];
// Increment each index from L to
// R in a[] by (j - l + 1)
for (int j = l; j <= r; j++) {
a[j] += (j - l + 1);
}
}
// Print the modified array
for (int i = 1; i <= N; i++) {
cout << a[i] << " ";
}
}
// Driver Code
int main()
{
int N = 7;
vector<vector<int> > queries
= { { 1, 7 }, { 3, 6 }, { 4, 5 } };
// Function Call
updateQuery(queries, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to perform the given queries
// in the given empty array of size N
static void updateQuery(int [][]queries, int N)
{
// Initialize an array a[]
ArrayList<Integer> a = new ArrayList<Integer>();
for(int i = 0; i < N + 1; i++)
a.add(0);
// Stores the size of the array
int q = 3;
// Traverse the queries
for(int i = 0; i < q; i++)
{
// Starting index
int l = queries[i][0];
// Ending index
int r = queries[i][1];
// Increment each index from L to
// R in a[] by (j - l + 1)
for(int j = l; j <= r; j++)
{
a.set(j, a.get(j)+(j - l + 1));
}
}
// Print the modified array
for(int i = 1; i < a.size(); i++)
{
System.out.print(a.get(i) + " ");
}
}
// Driver code
public static void main(String[] args)
{
int N = 7;
int[][] queries = { { 1, 7 },
{ 3, 6 },
{ 4, 5 } };
// Function Call
updateQuery(queries, N);
}
}
// This code is contributed by offbeat
Python3
# Python 3 program for the above approach # Function to perform the given queries # in the given empty array of size N def updateQuery(queries, N): # Initialize an array a[] a = [0 for i in range(N + 1)] # Stores the size of the array n = N + 1 q = len(queries) # Traverse the queries for i in range(q): # Starting index l = queries[i][0] # Ending index r = queries[i][1] # Increment each index from L to # R in a[] by (j - l + 1) for j in range(l, r + 1, 1): a[j] += (j - l + 1) # Print the modified array for i in range(1, N + 1, 1): print(a[i], end = " ") # Driver Code if __name__ == '__main__': N = 7 queries = [[1, 7],[3, 6],[4, 5]] # Function Call updateQuery(queries, N) # This code is contributed by ipg2016107.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to perform the given queries
// in the given empty array of size N
static void updateQuery(int [,]queries, int N)
{
// Initialize an array a[]
List<int> a = new List<int>();
for(int i = 0; i < N + 1; i++)
a.Add(0);
// Stores the size of the array
int q = 3;
// Traverse the queries
for(int i = 0; i < q; i++)
{
// Starting index
int l = queries[i, 0];
// Ending index
int r = queries[i, 1];
// Increment each index from L to
// R in a[] by (j - l + 1)
for(int j = l; j <= r; j++)
{
a[j] += (j - l + 1);
}
}
// Print the modified array
for(int i = 1; i < a.Count; i++)
{
Console.Write(a[i] + " ");
}
}
// Driver Code
public static void Main()
{
int N = 7;
int[,] queries = new int[3, 2] { { 1, 7 },
{ 3, 6 },
{ 4, 5 } };
// Function Call
updateQuery(queries, N);
}
}
// This code is contributed by SURENDRA_GANGWAR
Javascript
<script>
// JavaScript program for the above approach
// Function to perform the given queries
// in the given empty array of size N
function updateQuery(queries, N)
{
// Initialize an array a[]
let a = new Array(N + 1).fill(0);
// Stores the size of the array
let n = N + 1;
let q = queries.length;
// Traverse the queries
for (let i = 0; i < q; i++) {
// Starting index
let l = queries[i][0];
// Ending index
let r = queries[i][1];
// Increment each index from L to
// R in a[] by (j - l + 1)
for (let j = l; j <= r; j++) {
a[j] += (j - l + 1);
}
}
// Print the modified array
for (let i = 1; i <= N; i++) {
document.write(a[i]," ");
}
}
// Driver Code
let N = 7;
let queries = [ [ 1, 7 ], [ 3, 6 ], [ 4, 5 ] ];
// Function Call
updateQuery(queries, N);
// This code is contributed by shinjanpatra
</script>
Producción:
1 2 4 7 10 10 7
Complejidad temporal: O(N*Q)
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar mediante el uso de Prefix Sum . Siga los pasos a continuación para resolver este problema:
- Inicialice una array ans[] con todos los elementos como 0 para almacenar el número de veces que el índice actual se ve afectado por las consultas.
- Inicialice una array res[] con todos los elementos como 0 para almacenar el valor que se eliminará después de alcanzar el final de un cierto rango de consulta.
- Recorra la array dada de consultas query[] y realice los siguientes pasos:
- Agregue el 1 a ans[query[i][0]] y reste 1 de ans[query[i][1] + 1] .
- Resta (consulta[i][1] – consulta[i][0] + 1) de res[consulta[i][1] + 1] .
- Encuentre la suma del prefijo de la array ans[] .
- Recorra la array res[] y actualice cada elemento res[i] como res[i] + res[i – 1] + ans[i] .
- Después de completar los pasos anteriores, imprima la array res[] como la array modificada después de realizar las consultas dadas.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to perform the given queries
// in the given empty array of size N
void updateQuery(vector<vector<int> > queries,
int N)
{
// Stores the resultant array
// and the difference array
vector<int> ans(N + 2, 0),
res(N + 2, 0);
int q = queries.size();
// Traverse the given queries
for (int i = 0; i < q; i++) {
// Starting index
int l = queries[i][0];
// Ending index
int r = queries[i][1];
// Increment l-th index by 1
ans[l]++;
// Decrease r-th index by 1
ans[r + 1]--;
// Decrease (r + 1)th index by
// the length of each query
res[r + 1] -= (r - l + 1);
}
// Find the prefix sum of ans[]
for (int i = 1; i <= N; i++)
ans[i] += ans[i - 1];
// Find the final array
for (int i = 1; i <= N; i++)
res[i] += res[i - 1] + ans[i];
// Printing the modified array
for (int i = 1; i <= N; i++) {
cout << res[i] << " ";
}
cout << "\n";
}
// Driver Code
int main()
{
int N = 7;
vector<vector<int> > queries
= { { 1, 7 }, { 3, 6 }, { 4, 5 } };
updateQuery(queries, N);
return 0;
}
Java
// JAVA program for the above approach
import java.util.*;
class GFG
{
// Function to perform the given queries
// in the given empty array of size N
public static void
updateQuery(ArrayList<ArrayList<Integer> > queries,
int N)
{
// Stores the resultant array
// and the difference array
int ans[] = new int[N + 2];
int res[] = new int[N + 2];
for (int i = 0; i < N + 2; i++) {
ans[i] = 0;
res[i] = 0;
}
int q = queries.size();
// Traverse the given queries
for (int i = 0; i < q; i++) {
// Starting index
int l = queries.get(i).get(0);
// Ending index
int r = queries.get(i).get(1);
// Increment l-th index by 1
ans[l]++;
// Decrease r-th index by 1
ans[r + 1]--;
// Decrease (r + 1)th index by
// the length of each query
res[r + 1] -= (r - l + 1);
}
// Find the prefix sum of ans[]
for (int i = 1; i <= N; i++)
ans[i] += ans[i - 1];
// Find the final array
for (int i = 1; i <= N; i++)
res[i] += res[i - 1] + ans[i];
// Printing the modified array
for (int i = 1; i <= N; i++) {
System.out.print(res[i] + " ");
}
System.out.println();
}
// Driver Code
public static void main(String[] args)
{
int N = 7;
ArrayList<ArrayList<Integer> > queries
= new ArrayList<ArrayList<Integer> >();
ArrayList<Integer> temp1
= new ArrayList<Integer>(Arrays.asList(1, 7));
ArrayList<Integer> temp2
= new ArrayList<Integer>(Arrays.asList(3, 6));
ArrayList<Integer> temp3
= new ArrayList<Integer>(Arrays.asList(4, 5));
queries.add(temp1);
queries.add(temp2);
queries.add(temp3);
updateQuery(queries, N);
}
}
// This code is contributed by Taranpreet.
Python3
# Python 3 program for the above approach
# Function to perform the given queries
# in the given empty array of size N
def updateQuery(queries, N):
# Stores the resultant array
# and the difference array
ans = [0] * (N + 2)
res = [0] * (N + 2)
q = len(queries)
# Traverse the given queries
for i in range(q):
# Starting index
l = queries[i][0]
# Ending index
r = queries[i][1]
# Increment l-th index by 1
ans[l] += 1
# Decrease r-th index by 1
ans[r + 1] -= 1
# Decrease (r + 1)th index by
# the length of each query
res[r + 1] -= (r - l + 1)
# Find the prefix sum of ans[]
for i in range(1, N+1):
ans[i] += ans[i - 1]
# Find the final array
for i in range(1, N+1):
res[i] += res[i - 1] + ans[i]
# Printing the modified array
for i in range(1, N+1):
print(res[i], end=" ")
print("\n")
# Driver Code
if __name__ == '__main__':
N = 7
queries = [[1, 7], [3, 6], [4, 5]]
updateQuery(queries, N)
# This code is contributed by Anvesh Govind Saxena
Producción
1 2 4 7 10 10 7
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por dineshbs444 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA