Dada una array arr[] que consta de N enteros y una array Consultas[] que consta de Q consultas del tipo {X, L, R} para realizar las siguientes operaciones:
- Si el valor de X es 1 , actualice el elemento de la array en el índice X a L .
- De lo contrario, encuentre el índice mínimo j en el rango [L, R] tal que arr[j] ≥ X . Si no existe tal j , imprima “-1” .
Ejemplos:
Entrada: arr[] = {1, 3, 2, 4, 6}, Consultas[][] = {{2, 0, 4}, {1, 2, 5}, {4, 0, 4}, { 0, 0, 4}}
Salida: 1 2 0
Explicación:
Consulta 1: find(2, 0, 4) => El primer elemento que es al menos 2 es 3. Entonces, su índice es 1.
Consulta 2: actualizar(2 , 5) => arr[] = {1, 3, 5, 4, 6}.
Consulta 3: find(4, 0, 4) => El primer elemento que es al menos 4 es 5. Entonces, su índice es 2.
Consulta 4: find(0, 0, 4) => El primer elemento que es al menos 0 es 1. Entonces, su índice es 0.Entrada: arr[] = {1}, Consultas[][] = {{2, 0, 0}};
Salida: 1 2 0
Explicación:
Consulta 1: find(2, 0, 0) => Ningún elemento es mayor que 2. Por lo tanto, imprime -1.
Enfoque ingenuo: el enfoque más simple es recorrer la array para cada consulta. Para las consultas de Tipo 1 , actualice A[X ] a L. Para la consulta de Tipo 2 , recorra la array arr[] sobre el rango [L, R] y encuentre el índice mínimo j que satisfaga la condición. Si no se encuentra dicho índice, imprima “-1” .
Complejidad temporal: O(N*Q)
Espacio auxiliar: O(N)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar el árbol de segmentos para realizar consultas de manera eficiente. Siga los pasos a continuación para resolver el problema:
- Construya un árbol de segmentos donde cada Node representará el valor máximo en el rango de ese Node. Por ejemplo, para cualquier rango dado [i, j] , su Node correspondiente contendrá el valor máximo en ese rango.
- Inicialice una variable, digamos ans .
- Ahora, para consultas de tipo 2, si el rango actual no se encuentra dentro del rango [L, R] , entonces recorra su subárbol izquierdo.
- Ahora, en el subárbol izquierdo, si el máximo excede X y el rango actual se encuentra dentro del rango [L, R] , vaya al punto medio de ese rango y verifique si su valor es mayor que X o no. Si es cierto, visite su parte izquierda. De lo contrario, visite su parte derecha.
- Actualice la variable ans como el índice mínimo entre el rango dado, si existe.
- Continúe con los pasos anteriores, hasta que la parte izquierda del rango sea igual a la parte derecha.
- Después de completar los pasos anteriores, imprima el valor de ans como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
#define maxN 100
using namespace std;
// Stores nodes value of the Tree
int Tree[4 * maxN];
// Function to build segment tree
void build(int arr[], int index,
int s, int e)
{
// Base Case
if (s == e)
Tree[index] = arr[s];
else {
// Find the value of mid
int m = (s + e) / 2;
// Update for left subtree
build(arr, 2 * index, s, m);
// Update for right subtree
build(arr, 2 * index + 1,
m + 1, e);
// Update the value at the
// current index
Tree[index]
= max(Tree[2 * index],
Tree[2 * index + 1]);
}
}
// Function for finding the index
// of the first element at least x
int atleast_x(int index, int s, int e,
int ql, int qr, int x)
{
// If current range does
// not lie in query range
if (ql > e || qr < s)
return -1;
// If current range is inside
// of query range
if (s <= ql && e <= qr) {
// Maximum value in this
// range is less than x
if (Tree[index] < x)
return -1;
// Finding index of first
// value in this range
while (s != e) {
int m = (s + e) / 2;
// Update the value of
// the minimum index
if (Tree[2 * index] >= x) {
e = m;
index = 2 * index;
}
else {
s = m + 1;
index = 2 * index + 1;
}
}
return s;
}
// Find mid of the current range
int m = (s + e) / 2;
// Left subtree
int val = atleast_x(2 * index, s,
m, ql, qr, x);
if (val != -1)
return val;
// If it does not lie in
// left subtree
return atleast_x(2 * index + 1, m + 1,
e, ql, qr, x);
}
// Function for updating segment tree
void update(int index, int s, int e,
int new_val, int pos)
{
// Update the value, we
// reached leaf node
if (s == e)
Tree[index] = new_val;
else {
// Find the mid
int m = (s + e) / 2;
if (pos <= m) {
// If pos lies in the
// left subtree
update(2 * index, s, m,
new_val, pos);
}
else {
// pos lies in the
// right subtree
update(2 * index + 1,
m + 1, e,
new_val, pos);
}
// Update the maximum value
// in the range
Tree[index]
= max(Tree[2 * index],
Tree[2 * index + 1]);
}
}
// Function to print the answer
// for the given queries
void printAnswer(int* arr, int n)
{
// Build segment tree
build(arr, 1, 0, n - 1);
// Find index of first value
// atleast 2 in range [0, n-1]
cout << atleast_x(1, 0, n - 1,
0, n - 1, 2)
<< "\n";
// Update value at index 2 to 5
arr[2] = 5;
update(1, 0, n - 1, 5, 2);
// Find index of first value
// atleast 4 in range [0, n-1]
cout << atleast_x(1, 0, n - 1,
0, n - 1, 4)
<< "\n";
// Find index of first value
// atleast 0 in range [0, n-1]
cout << atleast_x(1, 0, n - 1,
0, n - 1, 0)
<< "\n";
}
// Driver Code
int main()
{
int arr[] = { 1, 3, 2, 4, 6 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
printAnswer(arr, N);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG
{
static int maxN = 100;
// Stores nodes value of the Tree
static int Tree[] = new int[4 * maxN];
// Function to build segment tree
static void build(int arr[], int index,
int s, int e)
{
// Base Case
if (s == e)
Tree[index] = arr[s];
else
{
// Find the value of mid
int m = (s + e) / 2;
// Update for left subtree
build(arr, 2 * index, s, m);
// Update for right subtree
build(arr, 2 * index + 1,
m + 1, e);
// Update the value at the
// current index
Tree[index]
= Math.max(Tree[2 * index],
Tree[2 * index + 1]);
}
}
// Function for finding the index
// of the first element at least x
static int atleast_x(int index, int s, int e,
int ql, int qr, int x)
{
// If current range does
// not lie in query range
if (ql > e || qr < s)
return -1;
// If current range is inside
// of query range
if (s <= ql && e <= qr) {
// Maximum value in this
// range is less than x
if (Tree[index] < x)
return -1;
// Finding index of first
// value in this range
while (s != e) {
int m = (s + e) / 2;
// Update the value of
// the minimum index
if (Tree[2 * index] >= x) {
e = m;
index = 2 * index;
}
else {
s = m + 1;
index = 2 * index + 1;
}
}
return s;
}
// Find mid of the current range
int m = (s + e) / 2;
// Left subtree
int val = atleast_x(2 * index, s,
m, ql, qr, x);
if (val != -1)
return val;
// If it does not lie in
// left subtree
return atleast_x(2 * index + 1, m + 1,
e, ql, qr, x);
}
// Function for updating segment tree
static void update(int index, int s, int e,
int new_val, int pos)
{
// Update the value, we
// reached leaf node
if (s == e)
Tree[index] = new_val;
else
{
// Find the mid
int m = (s + e) / 2;
if (pos <= m)
{
// If pos lies in the
// left subtree
update(2 * index, s, m,
new_val, pos);
}
else
{
// pos lies in the
// right subtree
update(2 * index + 1,
m + 1, e,
new_val, pos);
}
// Update the maximum value
// in the range
Tree[index]
= Math.max(Tree[2 * index],
Tree[2 * index + 1]);
}
}
// Function to print the answer
// for the given queries
static void printAnswer(int[] arr, int n)
{
// Build segment tree
build(arr, 1, 0, n - 1);
// Find index of first value
// atleast 2 in range [0, n-1]
System.out.println(atleast_x(1, 0, n - 1,
0, n - 1, 2));
// Update value at index 2 to 5
arr[2] = 5;
update(1, 0, n - 1, 5, 2);
// Find index of first value
// atleast 4 in range [0, n-1]
System.out.println(atleast_x(1, 0, n - 1,
0, n - 1, 4));
// Find index of first value
// atleast 0 in range [0, n-1]
System.out.println(atleast_x(1, 0, n - 1,
0, n - 1, 0));
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 1, 3, 2, 4, 6 };
int N = arr.length;
// Function Call
printAnswer(arr, N);
}
}
// This code is contributed by susmitakundugoaldanga.
Python3
# Python 3 program for the above approach maxN = 100 # Stores nodes value of the Tree Tree = [0 for i in range(4 * maxN)] # Function to build segment tree def build(arr, index, s, e): # Base Case global Tree global max if (s == e): Tree[index] = arr[s] else: # Find the value of mid m = (s + e) // 2 # Update for left subtree build(arr, 2 * index, s, m) # Update for right subtree build(arr, 2 * index + 1, m + 1, e) # Update the value at the # current index Tree[index] = max(Tree[2 * index], Tree[2 * index + 1]) # Function for finding the index # of the first element at least x def atleast_x(index, s, e, ql, qr, x): global Tree global max # If current range does # not lie in query range if (ql > e or qr < s): return -1 # If current range is inside # of query range if (s <= ql and e <= qr): # Maximum value in this # range is less than x if (Tree[index] < x): return -1; # Finding index of first # value in this range while (s != e): m = (s + e) // 2 # Update the value of # the minimum index if (Tree[2 * index] >= x): e = m index = 2 * index else: s = m + 1 index = 2 * index + 1 return s # Find mid of the current range m = (s + e) // 2 # Left subtree val = atleast_x(2 * index, s, m, ql, qr, x) if (val != -1): return val # If it does not lie in # left subtree return atleast_x(2 * index + 1, m + 1,e, ql, qr, x) # Function for updating segment tree def update(index, s, e, new_val, pos): global Tree global max # Update the value, we # reached leaf node if (s == e): Tree[index] = new_val else: # Find the mid m = (s + e) // 2 if (pos <= m): # If pos lies in the # left subtree update(2 * index, s, m,new_val, pos) else: # pos lies in the # right subtree update(2 * index + 1, m + 1, e, new_val, pos) # Update the maximum value # in the range Tree[index] = max(Tree[2 * index], Tree[2 * index + 1]) # Function to print the answer # for the given queries def printAnswer(arr, n): global Tree global max # Build segment tree build(arr, 1, 0, n - 1) # Find index of first value # atleast 2 in range [0, n-1] print(atleast_x(1, 0, n - 1, 0, n - 1, 2)) # Update value at index 2 to 5 arr[2] = 5 update(1, 0, n - 1, 5, 2) # Find index of first value # atleast 4 in range [0, n-1] print(atleast_x(1, 0, n - 1, 0, n - 1, 4)) # Find index of first value # atleast 0 in range [0, n-1] print(atleast_x(1, 0, n - 1, 0, n - 1, 0)) # Driver Code if __name__ == '__main__': arr = [1, 3, 2, 4, 6] N = len(arr) # Function Call printAnswer(arr, N) # This code is contributed by bgangwar59.
C#
// C# program to implement
// the above approach
using System;
class GFG
{
static int maxN = 100;
// Stores nodes value of the Tree
static int[] Tree = new int[4 * maxN];
// Function to build segment tree
static void build(int[] arr, int index,
int s, int e)
{
// Base Case
if (s == e)
Tree[index] = arr[s];
else
{
// Find the value of mid
int m = (s + e) / 2;
// Update for left subtree
build(arr, 2 * index, s, m);
// Update for right subtree
build(arr, 2 * index + 1,
m + 1, e);
// Update the value at the
// current index
Tree[index]
= Math.Max(Tree[2 * index],
Tree[2 * index + 1]);
}
}
// Function for finding the index
// of the first element at least x
static int atleast_x(int index, int s, int e,
int ql, int qr, int x)
{
// If current range does
// not lie in query range
if (ql > e || qr < s)
return -1;
// If current range is inside
// of query range
if (s <= ql && e <= qr) {
// Maximum value in this
// range is less than x
if (Tree[index] < x)
return -1;
// Finding index of first
// value in this range
while (s != e) {
int m = (s + e) / 2;
// Update the value of
// the minimum index
if (Tree[2 * index] >= x) {
e = m;
index = 2 * index;
}
else {
s = m + 1;
index = 2 * index + 1;
}
}
return s;
}
// Find mid of the current range
int mm = (s + e) / 2;
// Left subtree
int val = atleast_x(2 * index, s,
mm, ql, qr, x);
if (val != -1)
return val;
// If it does not lie in
// left subtree
return atleast_x(2 * index + 1, mm + 1,
e, ql, qr, x);
}
// Function for updating segment tree
static void update(int index, int s, int e,
int new_val, int pos)
{
// Update the value, we
// reached leaf node
if (s == e)
Tree[index] = new_val;
else
{
// Find the mid
int m = (s + e) / 2;
if (pos <= m)
{
// If pos lies in the
// left subtree
update(2 * index, s, m,
new_val, pos);
}
else
{
// pos lies in the
// right subtree
update(2 * index + 1,
m + 1, e,
new_val, pos);
}
// Update the maximum value
// in the range
Tree[index]
= Math.Max(Tree[2 * index],
Tree[2 * index + 1]);
}
}
// Function to print the answer
// for the given queries
static void printAnswer(int[] arr, int n)
{
// Build segment tree
build(arr, 1, 0, n - 1);
// Find index of first value
// atleast 2 in range [0, n-1]
Console.WriteLine(atleast_x(1, 0, n - 1,
0, n - 1, 2));
// Update value at index 2 to 5
arr[2] = 5;
update(1, 0, n - 1, 5, 2);
// Find index of first value
// atleast 4 in range [0, n-1]
Console.WriteLine(atleast_x(1, 0, n - 1,
0, n - 1, 4));
// Find index of first value
// atleast 0 in range [0, n-1]
Console.WriteLine(atleast_x(1, 0, n - 1,
0, n - 1, 0));
}
// Driver code
static void Main()
{
int[] arr = { 1, 3, 2, 4, 6 };
int N = arr.Length;
// Function Call
printAnswer(arr, N);
}
}
// This code is contributed by sanjoy_62
Javascript
<script>
// Javascript program to implement the above approach
let maxN = 100;
// Stores nodes value of the Tree
let Tree = new Array(4 * maxN);
// Function to build segment tree
function build(arr, index, s, e)
{
// Base Case
if (s == e)
Tree[index] = arr[s];
else
{
// Find the value of mid
let m = parseInt((s + e) / 2, 10);
// Update for left subtree
build(arr, 2 * index, s, m);
// Update for right subtree
build(arr, 2 * index + 1,
m + 1, e);
// Update the value at the
// current index
Tree[index]
= Math.max(Tree[2 * index],
Tree[2 * index + 1]);
}
}
// Function for finding the index
// of the first element at least x
function atleast_x(index, s, e, ql, qr, x)
{
// If current range does
// not lie in query range
if (ql > e || qr < s)
return -1;
// If current range is inside
// of query range
if (s <= ql && e <= qr) {
// Maximum value in this
// range is less than x
if (Tree[index] < x)
return -1;
// Finding index of first
// value in this range
while (s != e) {
let m = parseInt((s + e) / 2, 10);
// Update the value of
// the minimum index
if (Tree[2 * index] >= x) {
e = m;
index = 2 * index;
}
else {
s = m + 1;
index = 2 * index + 1;
}
}
return s;
}
// Find mid of the current range
let m = parseInt((s + e) / 2, 10);
// Left subtree
let val = atleast_x(2 * index, s,
m, ql, qr, x);
if (val != -1)
return val;
// If it does not lie in
// left subtree
return atleast_x(2 * index + 1, m + 1,
e, ql, qr, x);
}
// Function for updating segment tree
function update(index, s, e, new_val, pos)
{
// Update the value, we
// reached leaf node
if (s == e)
Tree[index] = new_val;
else
{
// Find the mid
let m = parseInt((s + e) / 2, 10);
if (pos <= m)
{
// If pos lies in the
// left subtree
update(2 * index, s, m,
new_val, pos);
}
else
{
// pos lies in the
// right subtree
update(2 * index + 1,
m + 1, e,
new_val, pos);
}
// Update the maximum value
// in the range
Tree[index]
= Math.max(Tree[2 * index],
Tree[2 * index + 1]);
}
}
// Function to print the answer
// for the given queries
function printAnswer(arr, n)
{
// Build segment tree
build(arr, 1, 0, n - 1);
// Find index of first value
// atleast 2 in range [0, n-1]
document.write(atleast_x(1, 0, n - 1, 0, n - 1, 2) + "</br>");
// Update value at index 2 to 5
arr[2] = 5;
update(1, 0, n - 1, 5, 2);
// Find index of first value
// atleast 4 in range [0, n-1]
document.write(atleast_x(1, 0, n - 1, 0, n - 1, 4) + "</br>");
// Find index of first value
// atleast 0 in range [0, n-1]
document.write(atleast_x(1, 0, n - 1, 0, n - 1, 0) + "</br>");
}
let arr = [ 1, 3, 2, 4, 6 ];
let N = arr.length;
// Function Call
printAnswer(arr, N);
// This code is contributed by decode2207.
</script>
Producción:
1 2 0
Complejidad temporal: O(Q*log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por single__loop y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA