Dada una array A[] que consta de N enteros y Q consultas, diga Consulta[][] de la forma {L, R, a, d} tal que cada consulta representa el AP infinito con el primer término como a y diferencia común d . La tarea es imprimir la array actualizada después de realizar las consultas dadas de modo que para cada consulta {L, R, a, d} agregue el valor de (i – L + 1) el término de la progresión aritmética a A[i] para cada índice i sobre el rango [L, R] .
Ejemplos:
Entrada: A[]= {5, 4, 2, 8}, Q = 2, Consulta[][] = {{1, 2, 1, 3}, {1, 4, 4, 1}}
Salida: 10 13 8 15
Explicación: Las
siguientes son las consultas realizadas:
Consulta 1: La progresión aritmética es {1, 4, 7, …}. Después de agregar el primer término de la progresión al índice 1 y el segundo término de la progresión al índice 2, la array se modifica a {6, 8, 2, 8}.
Consulta 2: La progresión aritmética es {4, 5, 6, 7, 8, …}. Después de agregar 4 a A[1], 5 a A[2], 6 a A[3] y 7 a A[4], la array se modifica a {10, 13, 8 15}.
Por lo tanto, la array resultante es {10, 13, 8 15}.Entrada: A[] = {1, 2, 3, 4, 5}, Q = 3, Consulta[][] = {{1, 2, 1, 3}, {1, 3, 4, 1}, { 1, 4, 1, 2}}
Salida: 7 14 14 11 5
Enfoque: El problema dado se puede resolver iterando sobre el rango [L, R] en cada operación y agregando el término correspondiente de la progresión aritmética dada en cada índice i . Siga los pasos a continuación para resolver el problema:
- Atraviese la array , Query[][] usando la variable i y para cada consulta {L, R, a, d} realice los siguientes pasos:
- Recorre la array A[], en el rango [L – 1, R – 1] usando la variable j
- Agregue el valor de a al valor de A[j] .
- Incrementa el valor de a por d .
- Recorre la array A[], en el rango [L – 1, R – 1] usando la variable j
- Después de completar los pasos anteriores, imprima la array A[] como la array actualizada resultante.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <iostream>
using namespace std;
// Function to find array after performing
// the given query to the array elements
void addAP(int A[], int Q, int operations[2][4])
{
// Traverse the given query
for (int j = 0; j < 2; ++j)
{
int L = operations[j][0], R = operations[j][1], a = operations[j][2], d = operations[j][3];
int curr = a;
// Traverse the given array
for(int i = L - 1; i < R; i++){
// Update the value of A[i]
A[i] += curr;
// Update the value of curr
curr += d;
}
}
// Print the array elements
for (int i = 0; i < 4; ++i)
cout << A[i] << " ";
}
// Driver Code
int main() {
int A[] = {5, 4, 2, 8};
int Q = 2;
int Query[2][4] = {{1, 2, 1, 3}, {1, 4, 4, 1}};
// Function Call
addAP(A, Q, Query);
return 0;
}
// This code is contributed by shubhamsingh10.
C
// C program for the above approach
#include <stdio.h>
// Function to find array after performing
// the given query to the array elements
void addAP(int A[], int Q, int operations[2][4])
{
// Traverse the given query
for (int j = 0; j < 2; ++j)
{
int L = operations[j][0], R = operations[j][1], a = operations[j][2], d = operations[j][3];
int curr = a;
// Traverse the given array
for(int i = L - 1; i < R; i++){
// Update the value of A[i]
A[i] += curr;
// Update the value of curr
curr += d;
}
}
// Print the array elements
for (int i = 0; i < 4; ++i)
printf("%d ", A[i]);
}
// Driver Code
int main() {
int A[] = {5, 4, 2, 8};
int Q = 2;
int Query[2][4] = {{1, 2, 1, 3}, {1, 4, 4, 1}};
// Function Call
addAP(A, Q, Query);
return 0;
}
// This code is contributed by shubhamsingh10.
Java
// Java program for the above approach
class GFG {
// Function to find array after performing
// the given query to the array elements
public static void addAP(int A[], int Q, int[][] operations)
{
// Traverse the given query
for (int j = 0; j < 2; ++j) {
int L = operations[j][0], R = operations[j][1],
a = operations[j][2], d = operations[j][3];
int curr = a;
// Traverse the given array
for (int i = L - 1; i < R; i++) {
// Update the value of A[i]
A[i] += curr;
// Update the value of curr
curr += d;
}
}
// Print the array elements
for (int i = 0; i < 4; ++i)
System.out.print(A[i] + " ");
}
// Driver Code
public static void main(String args[])
{
int A[] = { 5, 4, 2, 8 };
int Q = 2;
int query[][] = { { 1, 2, 1, 3 }, { 1, 4, 4, 1 } };
// Function Call
addAP(A, Q, query);
}
}
// This code is contributed by _saurabh_jaiswal
Python3
# Python program for the above approach # Function to find array after performing # the given query to the array elements def addAP(A, Q, operations): # Traverse the given query for L, R, a, d in operations: curr = a # Traverse the given array for i in range(L-1, R): # Update the value of A[i] A[i] += curr # Update the value of curr curr += d # Print the array elements for i in A: print(i, end =' ') # Driver Code A = [5, 4, 2, 8] Q = 2 Query = [(1, 2, 1, 3), (1, 4, 4, 1)] # Function Call addAP(A, Q, Query)
C#
// C# program for the above approach
using System;
class GFG{
// Function to find array after performing
// the given query to the array elements
public static void addAP(int[] A, int Q,
int[,] operations)
{
// Traverse the given query
for(int j = 0; j < 2; ++j)
{
int L = operations[j, 0], R = operations[j, 1],
a = operations[j, 2], d = operations[j, 3];
int curr = a;
// Traverse the given array
for(int i = L - 1; i < R; i++)
{
// Update the value of A[i]
A[i] += curr;
// Update the value of curr
curr += d;
}
}
// Print the array elements
for(int i = 0; i < 4; ++i)
Console.Write(A[i] + " ");
}
// Driver code
public static void Main(string[] args)
{
int[] A = { 5, 4, 2, 8 };
int Q = 2;
int[,] query = { { 1, 2, 1, 3 },
{ 1, 4, 4, 1 } };
// Function Call
addAP(A, Q, query);
}
}
// This code is contributed by avijitmondal1998
Javascript
<script>
// Javascript program for the above approach
// Function to find array after performing
// the given query to the array elements
function addAP(A, Q, operations)
{
// Traverse the given query
for( let Q of operations)
{
let L = Q[0], R = Q[1], a = Q[2], d = Q[3]
curr = a
// Traverse the given array
for(let i = L - 1; i < R; i++){
// Update the value of A[i]
A[i] += curr
// Update the value of curr
curr += d
}
}
// Print the array elements
for (let i of A){
document.write(i + " ")
}
}
// Driver Code
let A = [5, 4, 2, 8]
let Q = 2
let Query = [[1, 2, 1, 3], [1, 4, 4, 1]]
// Function Call
addAP(A, Q, Query)
// This code is contributed by gfgking.
</script>
10 13 8 15
Complejidad temporal: O(N*Q)
Espacio auxiliar: O(1)
Enfoque eficiente : Declaremos 2 variables X, que representa todas las diferencias en ejecución, es decir (d1 + d2 + d3…) , y S, que es la suma acumulativa que representa la suma resultante de todos los AP aplicados en el índice {i-1}.
Entonces, la suma acumulada del nuevo índice {i} será:
1. X[i] =X[i-1] + X’ { corrección de la diferencia, es decir, el comienzo o el final de AP}
2. S[i] = S[ i-1] + S’ { corrección de la suma acumulada, es decir, al comienzo o al final de AP}
3. S[i] = S[i] + X[i]
4. Arr[i] = Arr[i] + S[i ]
A continuación se muestra la implementación del enfoque anterior:
C++14
// Code by Omkar Tripathi
#include<bits/stdc++.h>
const char nl = '\n';
using namespace std;
void mysolution(vector<int> &arr, vector<vector<int>> &query){
int n = arr.size();
// array used to simulate extra addition (d1 + d2 + d3 + d4...) we perform with every increment
vector<int> collective_D(n+1, 0);
/*
When we reach the end of AP we make correction of the extire sum of AP
for the element that sum is useless but because it is part of
S( variable we are using to take collective sum) so we make correction for the new index.
*/
vector<int> S_collective_correction(n+1,0);
int l, r, d, a, X=0, S=0;
/* Here X variable used keeps track of d1 + d2 + d3 ... numbers of parrarel AP we are using because if we look
carefully next element difference with current element is X ( d1 + d2 + d3 ... numbers of parrarel AP) */
/* The other part of sum is captured by S and we make collective correction at the end of AP */
for(auto q: query){
l = q[0]; r = q[1]; a = q[2]; d = q[3];
r--;
collective_D[l] += d;
collective_D[r+1] -= d;
S_collective_correction[l-1] += (a);
S_collective_correction[r+1] -= a + (r+1-l)*d;
}
for(int i = 0; i < n; i++){
X += collective_D[i]; // X denotes the current D ( d1 + d2 + d3.. ) that are running in parallel.
S += S_collective_correction[i]; // If some AP starts or ends this makes necessary correction.
S += X; // S is the ( a1 + a2+ a3) + (n1*d1 + n2*d2 + n3*d3)
arr[i] += (S);
}
for(int i: arr) cout<<i<<' ';
cout<<nl;
}
void solve(){
vector<int> v = {5,4,2,8};
// query format {l r, a, d}
vector<vector<int>> query = {{1,2,1,3},{1,4,4,1}};
mysolution(v, query);
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T = 1;
while(T--){
solve();
}
return 0;
}
// Code contributed by Omkar Tripathi
10 13 8 15
Complejidad de tiempo: max(O(q), O(N))
Complejidad de espacio: O(N)