Dada una array arr[] de N enteros y Q consultas. Cada consulta consta de 3 números enteros L , R y K . Puede pasar del índice i al índice i + 1 en un solo paso o permanecer en ese índice en particular en un solo paso. Puede pasar del índice L al R en un máximo de K pasos e imprimir la suma de cada número en el que estaba en cada paso, incluido el L-ésimo número. La tarea es maximizar la suma en un máximo de K movimientos. Si no podemos movernos de L a R enK pasos y luego escriba “No” .
Ejemplos:
Entrada: arr[] = {1, 3, 2, -4, -5}, q = {
{0, 2, 2},
{0, 2, 4},
{3, 4, 1},
{0, 4, 2}}
Salida:
6
12
-9
No
Para la primera consulta:
En el primer paso, muévase del índice 0 al índice 1, por lo tanto, 1 + 3 = 4
En el segundo paso, muévase del índice 1 al índice 2, por lo tanto, 4 + 2 = 6
Para la segunda consulta:
En el primer paso, muévase del índice 0 al índice 1, por lo tanto, 1 + 3 = 4
En el segundo paso, quédese en el índice 1, por lo tanto, 4 + 3 = 7
En el tercer paso, quédese nuevamente en el índice 1, por lo tanto, 7 + 3 = 10
En el cuarto paso, pase del primer índice al segundo índice solamente, por lo tanto, 10 + 2 = 12
Un enfoque ingenuo es verificar primero si L – R > K , si es así, no podemos movernos del índice L al R en K pasos. Iterar de L a R , obtener la suma de todos los elementos entre L y R . Luego encuentre el elemento máximo en el rango L y R y la respuesta será la suma de los elementos en el rango y (K – (R – L)) * máximo . Si el máximo es un número negativo, realizamos exactamente los movimientos R – L; de lo contrario, realizamos los pasos adicionales en el índice de número máximo en el rango [L, R] .
Complejidad de tiempo: O(R – L) por consulta.
Un enfoque eficiente es usar el árbol de segmentos en el rango [L, R] para encontrar el número máximo y encontrar la suma en el rango usando el prefijo sum .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to create the tree
void tree(int low, int high, int pos,
int b[], int a[], int n)
{
// Leaf nodes
if (low == high) {
b[pos] = a[high];
return;
}
int mid = (high + low) / 2;
// Left subtree
tree(low, mid, 2 * pos + 1, b, a, n);
// Right subtree
tree(mid + 1, high, 2 * pos + 2, b, a, n);
// Merge the maximum
b[pos] = max(b[2 * pos + 1], b[2 * pos + 2]);
}
// Function that returns the maximum in range L and R
int rangemax(int s, int e, int low, int high,
int pos, int b[], int a[], int n)
{
// Complete overlap
if (low <= s && high >= e)
return b[pos];
// Out of range completely
if (e < low || s > high)
return INT_MIN;
int mid = (s + e) / 2;
// Find maximum in left and right subtrees
int left = rangemax(s, mid, low, high,
2 * pos + 1, b, a, n);
int right = rangemax(mid + 1, e, low, high,
2 * pos + 2, b, a, n);
// Return the maximum of both
return max(left, right);
}
// Function that solves a query
int solveQuery(int l, int r, int k, int n, int a[],
int b[], int prefix[])
{
// If there are ko
if (r - l > k)
return -1;
// Find maximum in range L and R
int maximum = rangemax(0, n - 1, l, r, 0, b, a, n);
// If maximum is 0
if (maximum < 0)
maximum = 0;
// Find the prefix sum
int rangesum = prefix[r];
// If not first element
if (l > 0)
rangesum -= prefix[l - 1];
// Get the answer
int answer = rangesum + (k - (r - l)) * maximum;
return answer;
}
// Function that solves the queries
void solveQueries(int n, int a[], int b[],
int prefix[], int queries[][3], int q)
{
// Solve all the queries
for (int i = 0; i < q; i++) {
int ans = solveQuery(queries[i][0], queries[i][1],
queries[i][2], n, a, b, prefix);
if (ans != -1)
cout << ans << endl;
else
cout << "No" << endl;
}
}
// Function to find the prefix sum
void findPrefixSum(int prefix[], int a[], int n)
{
prefix[0] = a[0];
for (int i = 1; i < n; i++) {
prefix[i] = prefix[i - 1] + a[i];
}
}
// Driver code
int main()
{
int a[] = { 1, 3, 2, -4, -5 };
int n = sizeof(a) / sizeof(a[0]);
// Array for segment tree
int b[5 * n];
// Create segment tree
tree(0, n - 1, 0, b, a, n);
int prefix[n];
// Fill prefix sum array
findPrefixSum(prefix, a, n);
// Queries
int queries[][3] = { { 0, 2, 2 },
{ 0, 2, 4 },
{ 3, 4, 1 },
{ 0, 4, 2 } };
int q = sizeof(queries) / sizeof(queries[0]);
solveQueries(n, a, b, prefix, queries, q);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function to create the tree
static void tree(int low, int high, int pos,
int b[], int a[], int n)
{
// Leaf nodes
if (low == high)
{
b[pos] = a[high];
return;
}
int mid = (high + low) / 2;
// Left subtree
tree(low, mid, 2 * pos + 1, b, a, n);
// Right subtree
tree(mid + 1, high, 2 * pos + 2, b, a, n);
// Merge the maximum
b[pos] = Math.max(b[2 * pos + 1], b[2 * pos + 2]);
}
// Function that returns the maximum in range L and R
static int rangemax(int s, int e, int low, int high,
int pos, int b[], int a[], int n)
{
// Complete overlap
if (low <= s && high >= e)
return b[pos];
// Out of range completely
if (e < low || s > high)
return Integer.MIN_VALUE;
int mid = (s + e) / 2;
// Find maximum in left and right subtrees
int left = rangemax(s, mid, low, high,
2 * pos + 1, b, a, n);
int right = rangemax(mid + 1, e, low, high,
2 * pos + 2, b, a, n);
// Return the maximum of both
return Math.max(left, right);
}
// Function that solves a query
static int solveQuery(int l, int r, int k, int n, int a[],
int b[], int prefix[])
{
// If there are ko
if (r - l > k)
return -1;
// Find maximum in range L and R
int maximum = rangemax(0, n - 1, l, r, 0, b, a, n);
// If maximum is 0
if (maximum < 0)
maximum = 0;
// Find the prefix sum
int rangesum = prefix[r];
// If not first element
if (l > 0)
rangesum -= prefix[l - 1];
// Get the answer
int answer = rangesum + (k - (r - l)) * maximum;
return answer;
}
// Function that solves the queries
static void solveQueries(int n, int a[], int b[],
int prefix[], int queries[][], int q)
{
// Solve all the queries
for (int i = 0; i < q; i++)
{
int ans = solveQuery(queries[i][0], queries[i][1],
queries[i][2], n, a, b, prefix);
if (ans != -1)
System.out.println(ans);
else
System.out.println("No" );
}
}
// Function to find the prefix sum
static void findPrefixSum(int prefix[], int a[], int n)
{
prefix[0] = a[0];
for (int i = 1; i < n; i++)
{
prefix[i] = prefix[i - 1] + a[i];
}
}
// Driver code
public static void main(String[] args)
{
int a[] = { 1, 3, 2, -4, -5 };
int n = a.length;
// Array for segment tree
int b[] = new int[5 * n];
// Create segment tree
tree(0, n - 1, 0, b, a, n);
int prefix[] = new int[n];
// Fill prefix sum array
findPrefixSum(prefix, a, n);
// Queries
int queries[][] = { { 0, 2, 2 },
{ 0, 2, 4 },
{ 3, 4, 1 },
{ 0, 4, 2 } };
int q = queries.length;
solveQueries(n, a, b, prefix, queries, q);
}
}
/* This code contributed by PrinciRaj1992 */
Python3
# Python3 implementation of the approach
# Function to create the tree
def tree( low, high, pos, b, a, n):
# Leaf nodes
if (low == high):
b[pos] = a[high]
return
mid = (high + low) // 2
# Left subtree
tree(low, mid, 2 * pos + 1, b, a, n)
# Right subtree
tree(mid + 1, high, 2 * pos + 2, b, a, n)
# Merge the maximum
b[pos] = max(b[2 * pos + 1], b[2 * pos + 2])
# Function that returns the maximum in range L and R
def rangemax(s, e, low, high, pos, b, a, n):
# Complete overlap
if (low <= s and high >= e):
return b[pos]
# Out of range completely
if (e < low or s > high):
return -(2**32)
mid = (s + e) // 2
# Find maximum in left and right subtrees
left = rangemax(s, mid, low, high, 2 * pos + 1, b, a, n)
right = rangemax(mid + 1, e, low, high, 2 * pos + 2, b, a, n)
# Return the maximum of both
return max(left, right)
# Function that solves a query
def solveQuery(l, r, k, n, a, b, prefix):
# If there are ko
if (r - l > k):
return -1
# Find maximum in range L and R
maximum = rangemax(0, n - 1, l, r, 0, b, a, n)
# If maximum is 0
if (maximum < 0):
maximum = 0
# Find the prefix sum
rangesum = prefix[r]
# If not first element
if (l > 0):
rangesum -= prefix[l - 1]
# Get the answer
answer = rangesum + (k - (r - l)) * maximum
return answer
# Function that solves the queries
def solveQueries( n, a, b, prefix, queries, q):
# Solve all the queries
for i in range(q):
ans = solveQuery(queries[i][0], queries[i][1],
queries[i][2], n, a, b, prefix)
if (ans != -1):
print(ans)
else:
print("No")
# Function to find the prefix sum
def findPrefixSum( prefix, a, n):
prefix[0] = a[0]
for i in range(1, n):
prefix[i] = prefix[i - 1] + a[i]
# Driver code
a = [1, 3, 2, -4, -5 ]
n = len(a)
# Array for segment tree
b = [0]*(5 * n)
# Create segment tree
tree(0, n - 1, 0, b, a, n)
prefix = [0]*n
# Fill prefix sum array
findPrefixSum(prefix, a, n)
# Queries
queries= [[0, 2, 2],[0, 2, 4],[3, 4, 1],[0, 4, 2]]
q = len(queries)
solveQueries(n, a, b, prefix, queries, q)
# This code is contributed by SHUBHAMSINGH10
C#
// C# program to implement
// the above approach
using System;
class GFG
{
// Function to create the tree
static void tree(int low, int high, int pos,
int []b, int []a, int n)
{
// Leaf nodes
if (low == high)
{
b[pos] = a[high];
return;
}
int mid = (high + low) / 2;
// Left subtree
tree(low, mid, 2 * pos + 1, b, a, n);
// Right subtree
tree(mid + 1, high, 2 * pos + 2, b, a, n);
// Merge the maximum
b[pos] = Math.Max(b[2 * pos + 1], b[2 * pos + 2]);
}
// Function that returns the maximum in range L and R
static int rangemax(int s, int e, int low, int high,
int pos, int []b, int []a, int n)
{
// Complete overlap
if (low <= s && high >= e)
return b[pos];
// Out of range completely
if (e < low || s > high)
return int.MinValue;
int mid = (s + e) / 2;
// Find maximum in left and right subtrees
int left = rangemax(s, mid, low, high,
2 * pos + 1, b, a, n);
int right = rangemax(mid + 1, e, low, high,
2 * pos + 2, b, a, n);
// Return the maximum of both
return Math.Max(left, right);
}
// Function that solves a query
static int solveQuery(int l, int r, int k, int n, int []a,
int []b, int []prefix)
{
// If there are ko
if (r - l > k)
return -1;
// Find maximum in range L and R
int maximum = rangemax(0, n - 1, l, r, 0, b, a, n);
// If maximum is 0
if (maximum < 0)
maximum = 0;
// Find the prefix sum
int rangesum = prefix[r];
// If not first element
if (l > 0)
rangesum -= prefix[l - 1];
// Get the answer
int answer = rangesum + (k - (r - l)) * maximum;
return answer;
}
// Function that solves the queries
static void solveQueries(int n, int []a, int []b,
int []prefix, int [,]queries, int q)
{
// Solve all the queries
for (int i = 0; i < q; i++)
{
int ans = solveQuery(queries[i,0], queries[i,1],
queries[i,2], n, a, b, prefix);
if (ans != -1)
Console.WriteLine(ans);
else
Console.WriteLine("No" );
}
}
// Function to find the prefix sum
static void findPrefixSum(int []prefix, int []a, int n)
{
prefix[0] = a[0];
for (int i = 1; i < n; i++)
{
prefix[i] = prefix[i - 1] + a[i];
}
}
// Driver code
public static void Main(String[] args)
{
int []a = { 1, 3, 2, -4, -5 };
int n = a.Length;
// Array for segment tree
int []b = new int[5 * n];
// Create segment tree
tree(0, n - 1, 0, b, a, n);
int []prefix = new int[n];
// Fill prefix sum array
findPrefixSum(prefix, a, n);
// Queries
int [,]queries = { { 0, 2, 2 },
{ 0, 2, 4 },
{ 3, 4, 1 },
{ 0, 4, 2 } };
int q = queries.GetLength(0);
solveQueries(n, a, b, prefix, queries, q);
}
}
// This code has been contributed by 29AjayKumar
Javascript
<script>
// JavaScript implementation of the approach
// Function to create the tree
function tree(low,high,pos,b,a,n)
{
// Leaf nodes
if (low == high)
{
b[pos] = a[high];
return;
}
let mid = Math.floor((high + low) / 2);
// Left subtree
tree(low, mid, 2 * pos + 1, b, a, n);
// Right subtree
tree(mid + 1, high, 2 * pos + 2, b, a, n);
// Merge the maximum
b[pos] = Math.max(b[2 * pos + 1], b[2 * pos + 2]);
}
// Function that returns the maximum in range L and R
function rangemax(s,e,low,high,pos,b,a,n)
{
// Complete overlap
if (low <= s && high >= e)
return b[pos];
// Out of range completely
if (e < low || s > high)
return Number.MIN_VALUE;
let mid = Math.floor((s + e) / 2);
// Find maximum in left and right subtrees
let left = rangemax(s, mid, low, high,
2 * pos + 1, b, a, n);
let right = rangemax(mid + 1, e, low, high,
2 * pos + 2, b, a, n);
// Return the maximum of both
return Math.max(left, right);
}
// Function that solves a query
function solveQuery(l,r,k,n,a,b,prefix)
{
// If there are ko
if (r - l > k)
return -1;
// Find maximum in range L and R
let maximum = rangemax(0, n - 1, l, r, 0, b, a, n);
// If maximum is 0
if (maximum < 0)
maximum = 0;
// Find the prefix sum
let rangesum = prefix[r];
// If not first element
if (l > 0)
rangesum -= prefix[l - 1];
// Get the answer
let answer = rangesum + (k - (r - l)) * maximum;
return answer;
}
// Function that solves the queries
function solveQueries(n,a,b,prefix,queries,q)
{
// Solve all the queries
for (let i = 0; i < q; i++)
{
let ans = solveQuery(queries[i][0], queries[i][1],
queries[i][2], n, a, b, prefix);
if (ans != -1)
document.write(ans+"<br>");
else
document.write("No<br>" );
}
}
// Function to find the prefix sum
function findPrefixSum(prefix,a,n)
{
prefix[0] = a[0];
for (let i = 1; i < n; i++)
{
prefix[i] = prefix[i - 1] + a[i];
}
}
// Driver code
let a=[1, 3, 2, -4, -5];
let n = a.length;
// Array for segment tree
let b = new Array(5 * n);
// Create segment tree
tree(0, n - 1, 0, b, a, n);
let prefix = new Array(n);
// Fill prefix sum array
findPrefixSum(prefix, a, n);
// Queries
let queries = [[ 0, 2, 2 ],
[ 0, 2, 4 ],
[ 3, 4, 1 ],
[ 0, 4, 2 ] ];
let q = queries.length;
solveQueries(n, a, b, prefix, queries, q);
// This code is contributed by rag2127
</script>
Producción:
6 12 -9 No
Complejidad de tiempo: O(Log N) por consulta.
Espacio Auxiliar: O(N log N)