Encuentre el elemento Array restante después de agregar valores en rangos dados

Dada una array A[] que contiene N elementos y una array de consultas que contiene Q consultas de tipo [ X, L, R ] donde X es el elemento que se agregará a todos los elementos en el rango [L, R] . Después de realizar todas las consultas Q , continúe eliminando dos elementos de la array y agregue su suma en la array hasta que el tamaño de la array sea 1. La tarea es encontrar este elemento restante de la array.

Nota: Se considera la indexación basada en 1.

Ejemplo:

Aporte: A[] = [ 1, 4, 3, 2, 4 ], consultas = [ [5, 1, 2 ], [ -5, 1, 3 ] ]
Salida: 9
Explicación: 
1ra consulta: sumando 5 a la primera y segundo elemento, A se convierte en {6, 9, 3, 2, 4}.
Segunda consulta: sumando -5 al primer, segundo y tercer elemento, A se convierte en {1, 4, -2, 2, 4}.
Operación 1: seleccione A1=1 y A3 = -2, elimínelos y 
agregue su suma (1-2=-1) a la array, A se convierte en {4, 2, 4, -1}.
Operación 2: seleccione A2=2 y A3 = -1, elimínelos y 
agregue su suma (2-1=1) a la array, A se convierte en {4, 4, 1}.
Operación 3: seleccione A1=4 y A3=1, elimínelos y 
agregue su suma (4+1=5) a la array, A se convierte en {4, 5}.
Operación 4: Seleccionar los dos elementos restantes y 
suma su suma (4+5 = 9) a la array, A se convierte en {9}.

Entrada:  A = [1, 2, 3], consultas = [ [-3, 1, 3 ] ]
Salida: -3

Enfoque ingenuo:

Primero calcule la array A para todas las consultas Q recorriéndolas y agregando queries[i][0] from queries[i][1]-1 to queries[i][2]-1 . 

Luego, la selección de los elementos debe ser aleatoria, pero es importante tener en cuenta que cualquier par de elementos (A _i y A _j ) que eliminamos y agregamos su suma ( A _i + A _j ) como nuevo elemento, estamos confirmados para obtener la suma de la array A como el último elemento restante debido a la propiedad de suma que se menciona a continuación:

S _norte (suma) = (UN ₁ + UN ₂ ) + UN ₃ + UN ₄ + . . . + UN _norte
S _norte = (S ₁₂ + UN ₃ ) + UN ₄ + . . . + Un
S _norte = (S ₁₂₃ + UN ₄ )+ . . . + un _n
         . . . . .
S _n = S _123…n

Siga la siguiente ilustración para una mejor comprensión

Ilustración:

Considere un ejemplo A = [a1, a2, a3] y consultas = [[x1, 1, 2], [x2, 1, 3]]

1ra consulta: 

Al sumar x1 al primer y segundo elemento,  
la array A se convierte en [a1 + x1, a2 + x1, a3] .
nuevo a1 = a1 + x1
nuevo a2 = a2 + x1

2ª consulta: 

Al agregar x2 al primer, segundo y tercer elemento,  
la array A se convierte en [a1 + x2, a2 ​​+ x2, a3 + x2] .
nuevo a1 = a1 + x2
nuevo a2 = a2 + x2 
nuevo a3 = a3 + x2       

Operación 1: 

Seleccione a1 y a3, elimínelos y agregue su suma (a1 + a3) a la array,  
A se convierte en [a2, (a1 + a3)].
a2 anterior se convierte en a1 y la suma añadida se convierte en a2.

Operación 2: 

Seleccione a1 y a2, elimínelos y agregue su suma (a1 + a2) a la array,  
A se convierte en [a1 + a2 + a3]

Siga los pasos mencionados a continuación para implementar la idea:

• Traverse para todas las consultas Q (digamos i) .
  • Pasar de consultas[i][1]-1 a consultas[i][2]-1 (digamos j) .
    • Agregue consultas [i] [0] a todos los elementos de la array en el rango.
• Después de que terminen todos los bucles, recorra la array A[] para encontrar la suma y almacenarla en result .
• Devuelve resultado como respuesta final.

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

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the value of the reamining element
int randomize(vector<int>& A, int& N,
              vector<vector<int> >& queries, int& Q)
{
    int result = 0;
 
    // Loop to perform the queries
    for (int i = 0; i < Q; i++) {
        for (int j = queries[i][1] - 1;
             j < queries[i][2]; j++)
            A[j] += queries[i][0];
    }
 
    // Loop to find the sum of the array
    for (int i = 0; i < N; i++)
        result += A[i];
 
    return result;
}
 
// Driver code
int main()
{
    vector<int> A = { 1, 4, 3, 2, 4 };
    int N = A.size();
    vector<vector<int> > queries
        = { { 5, 1, 2 }, { -5, 1, 3 } };
    int Q = queries.size();
 
    // Function call
    cout << randomize(A, N, queries, Q);
    return 0;
}

9

Complejidad Temporal: O(Q*M + N) donde M es el rango máximo entre las consultas
Espacio Auxiliar:O(1)

Enfoque eficiente:  el problema también se puede resolver de manera eficiente al reducir el requisito de tiempo de las actualizaciones de consultas. La idea es la siguiente.

Si vemos con claridad, podemos encontrar nuestra respuesta haciendo las cosas al revés. 

• Primero agregamos todos los elementos presentes en A en un elemento ans y luego,  
• Agregue los elementos presentes en las consultas al rango que se proporciona, es decir, simplemente agregue las consultas [i]*((LR)+1) a ans en lugar de aplicarlo al rango dado [L, R] .

Siga los pasos que se indican a continuación:

• Recorra A y agregue todos los elementos presentes en ella.
• Recorra las consultas y agregue consultas[i][0] * ((consultas[i][1]-consultas[i][2])+1) a la suma.
• Devuelve la suma como la respuesta requerida.

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

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the remaining value
int solve(vector<int>& v,
          vector<vector<int> >& queries)
{
    int ans = 0;
 
    // Loop to calculate the array sum
    for (int i = 0; i < v.size(); i++) {
        ans += v[i];
    }
 
    // Loop to process the queries
    for (int i = 0; i < queries.size(); i++) {
        int temp = abs(queries[i][1] - queries[i][2]) + 1;
        ans += queries[i][0] * temp;
    }
    return ans;
}
 
// Driver code
int main()
{
    vector<int> A = { 1, 4, 3, 2, 4 };
    int N = A.size();
    vector<vector<int> > queries
        = { { 5, 1, 2 }, { -5, 1, 3 } };
 
    // Function call
    cout << solve(A, queries);
    return 0;
}

// Java code to implement the approach
import java.io.*;
 
class GFG {
    // Function to find the remaining value
    public static int solve(int v[], int queries[][])
    {
        int ans = 0;
 
        // Loop to calculate the array sum
        for (int i = 0; i < v.length; i++) {
            ans += v[i];
        }
 
        // Loop to process the queries
        for (int i = 0; i < queries.length; i++) {
            int temp
                = Math.abs(queries[i][1] - queries[i][2])
                  + 1;
            ans += queries[i][0] * temp;
        }
        return ans;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int A[] = { 1, 4, 3, 2, 4 };
        int N = A.length;
        int queries[][] = { { 5, 1, 2 }, { -5, 1, 3 } };
 
        // Function call
        System.out.print(solve(A, queries));
    }
}
 
// This code is contributed by Rohit Pradhan

9

Complejidad del tiempo:O(N + Q)
Espacio Auxiliar:O(1)