Dada una array de tamaño ‘n’ y un conjunto dado de comandos de tamaño ‘m’. Cada comando consta de cuatro números enteros q, l, r, k. Estos comandos son de los siguientes tipos:
- Si q = 0, agregue ‘k’ a todos los enteros en el rango ‘a’ a ‘b’ (1 <= a <= b <= n).
- Si q = 1, reste ‘k’ a todos los números enteros en el rango ‘a’ a ‘b’ (1 <= a <= b <= n).
Nota : Inicialmente, todos los elementos de la array se establecen en ‘0’ y la indexación de la array es desde ‘1’.
Input : n = 5
commands[] = {{0 1 3 2}, {1 3 5 3},
{0 2 5 1}}
Output : 0 2 -1 -1 -3
Explanation
First command: Add 2 from index 1 to 3
>= 2 2 2 0 0
Second command: Subtract 3 from index 3 to 5
>= 2 2 -1 -3 -3
Third command: Add 1 from index 2 to 5
>= 2 3 0 -2 -2
El enfoque simple es ejecutar cada comando iterando desde el índice izquierdo (l) hasta el índice derecho (r) y actualizar cada índice de acuerdo con el comando dado. La complejidad temporal de este enfoque es O(n*m)
Un mejor enfoque es usar el árbol de Fenwick (BIT) o el árbol de segmentos. Pero solo optimizará hasta el tiempo de registro (n), es decir, la complejidad general se convertiría en O (m * registro (n))
El enfoque eficiente es usar matemáticas simples. Dado que todos los comandos se pueden manejar como fuera de línea, podemos almacenar todas las actualizaciones en nuestra array temporal y luego ejecutarlas en el último.
- Para el comando ‘ 0 ‘, agregue ‘ +k ‘ y ‘ -k ‘ en los elementos de índice lth y (r+1) th respectivamente.
- Para el comando ‘ 1 ‘, agregue ‘ -k ‘ y ‘ +k ‘ en los elementos de índice l th y (r+1) th respectivamente.
Después de eso, sume todos los elementos para cada índice ‘ i ‘ a partir del 1er índice, es decir, ai contendrá la suma de todos los elementos del 1 al i – ésimo índice. Esto se puede lograr fácilmente con la ayuda de la programación dinámica.
Implementación:
C++
// C++ program to find modified array
// after executing m commands/queries
#include<bits/stdc++.h>
using namespace std;
// Update function for every command
void updateQuery(int arr[], int n, int q, int l,
int r, int k)
{
// If q == 0, add 'k' and '-k'
// to 'l-1' and 'r' index
if (q == 0){
arr[l-1] += k;
arr[r] += -k;
}
// If q == 1, add '-k' and 'k'
// to 'l-1' and 'r' index
else{
arr[l-1] += -k;
arr[r] += k;
}
return;
}
// Function to generate the final
// array after executing all
// commands
void generateArray(int arr[], int n)
{
// Generate final array with the
// help of DP concept
for (int i = 1; i < n; ++i)
arr[i] += arr[i-1];
return;
}
// Driver program
int main()
{
int n = 5;
int arr[n+1];
//Set all array elements to '0'
memset(arr, 0, sizeof(arr));
int q = 0, l = 1, r = 3, k = 2;
updateQuery(arr, n, q, l, r, k);
q = 1 , l = 3, r = 5, k = 3;
updateQuery(arr, n, q, l, r, k);
q = 0 , l = 2, r = 5, k = 1;
updateQuery(arr, n, q, l, r, k);
// Generate final array
generateArray(arr, n);
// Printing the final modified array
for (int i = 0; i < n; ++i)
cout << arr[i] << " ";
return 0;
}
Java
// Java program to find modified array
// after executing m commands/queries
import java.util.Arrays;
class GFG {
// Update function for every command
static void updateQuery(int arr[], int n,
int q, int l, int r, int k)
{
// If q == 0, add 'k' and '-k'
// to 'l-1' and 'r' index
if (q == 0){
arr[l-1] += k;
arr[r] += -k;
}
// If q == 1, add '-k' and 'k'
// to 'l-1' and 'r' index
else{
arr[l-1] += -k;
arr[r] += k;
}
return;
}
// Function to generate the final
// array after executing all
// commands
static void generateArray(int arr[], int n)
{
// Generate final array with the
// help of DP concept
for (int i = 1; i < n; ++i)
arr[i] += arr[i-1];
}
//driver code
public static void main(String arg[])
{
int n = 5;
int arr[] = new int[n+1];
//Set all array elements to '0'
Arrays.fill(arr, 0);
int q = 0, l = 1, r = 3, k = 2;
updateQuery(arr, n, q, l, r, k);
q = 1 ; l = 3; r = 5; k = 3;
updateQuery(arr, n, q, l, r, k);
q = 0 ; l = 2; r = 5; k = 1;
updateQuery(arr, n, q, l, r, k);
// Generate final array
generateArray(arr, n);
// Printing the final modified array
for (int i = 0; i < n; ++i)
System.out.print(arr[i]+" ");
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python3 program to find modified array # after executing m commands/queries # Update function for every command def updateQuery(arr, n, q, l, r, k): # If q == 0, add 'k' and '-k' # to 'l-1' and 'r' index if (q == 0): arr[l - 1] += k arr[r] += -k # If q == 1, add '-k' and 'k' # to 'l-1' and 'r' index else: arr[l - 1] += -k arr[r] += k return # Function to generate the final # array after executing all commands def generateArray(arr, n): # Generate final array with the # help of DP concept for i in range(1, n): arr[i] += arr[i - 1] return # Driver Code n = 5 arr = [0 for i in range(n + 1)] # Set all array elements to '0' q = 0; l = 1; r = 3; k = 2 updateQuery(arr, n, q, l, r, k) q, l, r, k = 1, 3, 5, 3 updateQuery(arr, n, q, l, r, k); q, l, r, k = 0, 2, 5, 1 updateQuery(arr, n, q, l, r, k) # Generate final array generateArray(arr, n) # Printing the final modified array for i in range(n): print(arr[i], end = " ") # This code is contributed by Anant Agarwal.
C#
// Program to find modified
// array after executing
// m commands/queries
using System;
class GFG {
// Update function for every command
static void updateQuery(int[] arr, int n, int q,
int l, int r, int k)
{
// If q == 0, add 'k' and '-k'
// to 'l-1' and 'r' index
if (q == 0) {
arr[l - 1] += k;
arr[r] += -k;
}
// If q == 1, add '-k' and 'k'
// to 'l-1' and 'r' index
else {
arr[l - 1] += -k;
arr[r] += k;
}
return;
}
// Function to generate final
// array after executing all
// commands
static void generateArray(int[] arr, int n)
{
// Generate final array with
// the help of DP concept
for (int i = 1; i < n; ++i)
arr[i] += arr[i - 1];
}
// Driver code
public static void Main()
{
int n = 5;
int[] arr = new int[n + 1];
// Set all array elements to '0'
for (int i = 0; i < arr.Length; i++)
arr[i] = 0;
int q = 0, l = 1, r = 3, k = 2;
updateQuery(arr, n, q, l, r, k);
q = 1;
l = 3;
r = 5;
k = 3;
updateQuery(arr, n, q, l, r, k);
q = 0;
l = 2;
r = 5;
k = 1;
updateQuery(arr, n, q, l, r, k);
// Generate final array
generateArray(arr, n);
// Printing the final modified array
for (int i = 0; i < n; ++i)
Console.Write(arr[i] + " ");
}
}
// This code is contributed by Anant Agarwal.
Javascript
<script>
// javascript program to find modified array
// after executing m commands/queries
// Update function for every command
function updateQuery(arr , n , q , l , r , k) {
// If q == 0, add 'k' and '-k'
// to 'l-1' and 'r' index
if (q == 0) {
arr[l - 1] += k;
arr[r] += -k;
}
// If q == 1, add '-k' and 'k'
// to 'l-1' and 'r' index
else {
arr[l - 1] += -k;
arr[r] += k;
}
return;
}
// Function to generate the final
// array after executing all
// commands
function generateArray(arr, n)
{
// Generate final array with the
// help of DP concept
for (i = 1; i < n; ++i)
arr[i] += arr[i - 1];
}
// Driver code
var n = 5;
var arr = Array(n + 1).fill(0);
var q = 0, l = 1, r = 3, k = 2;
updateQuery(arr, n, q, l, r, k);
q = 1;
l = 3;
r = 5;
k = 3;
updateQuery(arr, n, q, l, r, k);
q = 0;
l = 2;
r = 5;
k = 1;
updateQuery(arr, n, q, l, r, k);
// Generate final array
generateArray(arr, n);
// Printing the final modified array
for (i = 0; i < n; i++)
document.write(arr[i] + " ");
// This code is contributed by aashish1995
</script>
2 3 0 -2 -2
Complejidad temporal: O(Max(m,n))
Espacio auxiliar: O(n)
Este artículo es una contribución de Shubham Bansal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA