Dada una array arr[] de tamaño N y una array 2D Q[][] que consta de consultas de los siguientes dos tipos:
- 1 XY: actualice el elemento de array en el índice X con Y.
- 2 K: Imprime la posición del primer elemento de la array mayor o igual que K . Si no existe tal índice, imprima -1 .
Ejemplos:
Entrada : arr[] = { 1, 3, 2, 4, 6 }, Q[][] = {{2, 5}, {1, 3, 5}, {2, 4}, {2, 8} }
Salida : 5 3 -1
Explicación:
Consulta1: Dado que arr[4] > 5, la posición de arr[4] es 5.
Consulta2: Actualizar arr[2] con 5 modifica arr[] a {1, 3, 5, 4, 6}
Consulta3: Dado que arr[2] > 4, la posición de arr[4] es 5.
Consulta4: Ningún elemento de la array es mayor que 8.Entrada : arr[] = {1, 2, 3}, N = 3, Q[][] = {{2, 2}, {1, 3, 5}, {2, 10}} Salida:
2 -1
Enfoque ingenuo: el enfoque más simple para resolver este problema es el siguiente:
- Para una consulta de tipo 1 , actualice arr[X – 1 ] a Y.
- De lo contrario, recorra la array e imprima la posición del primer elemento de la array que es mayor o igual que K .
Complejidad de tiempo: O(N * |Q|)
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar utilizando el árbol de segmentos . La idea es construir y actualizar el árbol utilizando el concepto de consulta de rango máximo con actualización de Node . Siga los pasos a continuación para resolver el problema:
- Construya un árbol de segmentos con cada Node compuesto por el máximo de su subárbol.
- La operación de actualización se puede realizar utilizando el concepto de consulta de rango máximo con actualización de Node
- La posición del primer elemento de la array que es mayor o igual a K se puede encontrar verificando recursivamente las siguientes condiciones:
- Compruebe si la raíz del subárbol izquierdo es mayor o igual que K o no. Si se encuentra que es cierto, busque la posición en el subárbol izquierdo. Si no se encuentra ningún elemento de array en el subárbol izquierdo, busque recursivamente la posición en el subárbol derecho.
- De lo contrario, encuentre recursivamente la posición en el subárbol derecho.
- Finalmente, imprima la posición de un elemento de array que sea mayor o igual a K .
A continuación se muestra la implementación del enfoque anterior :
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the mid
// of start and end
int getMid(int s, int e) { return s + (e - s) / 2; }
// Function to update nodes at position index
void updateValue(int arr[], int* st, int ss, int se,
int index, int value, int node)
{
// If index is out of range
if (index < ss || index > se) {
cout << "Invalid Input" << endl;
return;
}
// If a leaf node is found
if (ss == se) {
// update value in array
arr[index] = value;
// Update value in
// the segment tree
st[node] = value;
}
else {
// Stores mid of ss and se
int mid = getMid(ss, se);
// If index is less than or
// equal to mid
if (index >= ss && index <= mid) {
// Recursively call for left subtree
updateValue(arr, st, ss, mid, index, value,
2 * node + 1);
}
else {
// Recursively call for right subtree
updateValue(arr, st, mid + 1, se, index, value,
2 * node + 2);
}
// Update st[node]
st[node] = max(st[2 * node + 1], st[2 * node + 2]);
}
return;
}
// Function to find the position of first element
// which is greater than or equal to X
int findMinimumIndex(int* st, int ss, int se, int K, int si)
{
// If no such element found in current
// subtree which is greater than or
// equal to K
if (st[si] < K)
return 1e9;
// If current node is leaf node
if (ss == se) {
// If value of current node
// is greater than or equal to X
if (st[si] >= K) {
return ss;
}
return 1e9;
}
// Stores mid of ss and se
int mid = getMid(ss, se);
int l = 1e9;
// If root of left subtree is
// greater than or equal to K
if (st[2 * si + 1] >= K)
l = min(l, findMinimumIndex(st, ss, mid, K,
2 * si + 1));
// If no such array element is
// found in the left subtree
if (l == 1e9 && st[2 * si + 2] >= K)
l = min(l, findMinimumIndex(st, mid + 1, se, K,
2 * si + 2));
return l;
}
// Function to build a segment tree
int Build(int arr[], int ss, int se, int* st, int si)
{
// If current node is leaf node
if (ss == se) {
st[si] = arr[ss];
return arr[ss];
}
// store mid of ss and se
int mid = getMid(ss, se);
// Stores maximum of left subtree and rightsubtree
st[si] = max(Build(arr, ss, mid, st, si * 2 + 1),
Build(arr, mid + 1, se, st, si * 2 + 2));
return st[si];
}
// Function to initialize a segment tree
// for the given array
int* constructST(int arr[], int n)
{
// Height of segment tree
int x = (int)(ceil(log2(n)));
// Maximum size of segment tree
int max_size = 2 * (int)pow(2, x) - 1;
// Allocate memory
int* st = new int[max_size];
// Fill the allocated memory st
Build(arr, 0, n - 1, st, 0);
// Return the constructed segment tree
return st;
}
// Function to perform the queries of
// the given type
void PerformQueries(int arr[], int N,
vector<vector<int> > Q)
{
// Build segment tree for the given array
int* st = constructST(arr, N);
// Traverse the query array
for (int i = 0; i < Q.size(); i++) {
// If query of type 1 found
if (Q[i][0] == 1)
updateValue(arr, st, 0, N - 1, Q[i][1] - 1, 5,
0);
else {
// Stores index of first array element
// which is greater than or equal
// to Q[i][1]
int f = findMinimumIndex(st, 0, N - 1, Q[i][1],
0);
if (f < N)
cout << f + 1 << " ";
else
cout << -1 << " ";
}
}
}
// Driver Code
int main()
{
int arr[] = { 1, 3, 2, 4, 6 };
vector<vector<int> > Q{
{ 2, 5 }, { 1, 3, 5 }, { 2, 4 }, { 2, 8 }
};
int N = sizeof(arr) / sizeof(arr[0]);
PerformQueries(arr, N, Q);
return 0;
}
Java
// Java program to implement
// the above approach
import java.io.*;
class GFG
{
// Function to find the mid
// of start and end
static int getMid(int s, int e)
{
return s + (e - s) / 2;
}
static void updateValue(int arr[], int[] st, int ss,
int se, int index, int value,
int node)
{
// If index is out of range
if (index < ss || index > se)
{
System.out.println("Invalid Input");
return;
}
// If a leaf node is found
if (ss == se)
{
// update value in array
arr[index] = value;
// Update value in
// the segment tree
st[node] = value;
}
else
{
// Stores mid of ss and se
int mid = getMid(ss, se);
// If index is less than or
// equal to mid
if (index >= ss && index <= mid)
{
// Recursively call for left subtree
updateValue(arr, st, ss, mid, index, value,
2 * node + 1);
}
else
{
// Recursively call for right subtree
updateValue(arr, st, mid + 1, se, index,
value, 2 * node + 2);
}
// Update st[node]
st[node] = Math.max(st[2 * node + 1],
st[2 * node + 2]);
}
}
// Function to find the position of first element
// which is greater than or equal to X
static int findMinimumIndex(int[] st, int ss, int se,
int K, int si)
{
// If no such element found in current
// subtree which is greater than or
// equal to K
if (st[si] < K)
return 1000000000;
// If current node is leaf node
if (ss == se)
{
// If value of current node
// is greater than or equal to X
if (st[si] >= K)
{
return ss;
}
return 1000000000;
}
// Stores mid of ss and se
int mid = getMid(ss, se);
int l = 1000000000;
// If root of left subtree is
// greater than or equal to K
if (st[2 * si + 1] >= K)
l = Math.min(l, findMinimumIndex(st, ss, mid, K,
2 * si + 1));
// If no such array element is
// found in the left subtree
if (l == 1e9 && st[2 * si + 2] >= K)
l = Math.min(l,
findMinimumIndex(st, mid + 1, se,
K, 2 * si + 2));
return l;
}
// Function to build a segment tree
static int Build(int arr[], int ss, int se, int[] st,
int si)
{
// If current node is leaf node
if (ss == se)
{
st[si] = arr[ss];
return arr[ss];
}
// store mid of ss and se
int mid = getMid(ss, se);
// Stores maximum of left subtree and rightsubtree
st[si] = Math.max(
Build(arr, ss, mid, st, si * 2 + 1),
Build(arr, mid + 1, se, st, si * 2 + 2));
return st[si];
}
// Function to initialize a segment tree
// for the given array
static int[] constructST(int arr[], int n)
{
// Height of segment tree
int x = (int)Math.ceil(Math.log(n) / Math.log(2));
// Maximum size of segment tree
int max_size = 2 * (int)Math.pow(2, x) - 1;
// Allocate memory
int[] st = new int[max_size];
// Fill the allocated memory st
Build(arr, 0, n - 1, st, 0);
// Return the constructed segment tree
return st;
}
static void PerformQueries(int arr[], int N, int[][] Q)
{
// Build segment tree for the given array
int[] st = constructST(arr, N);
// Traverse the query array
for (int i = 0; i < Q.length; i++)
{
// If query of type 1 found
if (Q[i][0] == 1)
updateValue(arr, st, 0, N - 1, Q[i][1] - 1,
5, 0);
else {
// Stores index of first array element
// which is greater than or equal
// to Q[i][1]
int f = findMinimumIndex(st, 0, N - 1,
Q[i][1], 0);
if (f < N)
System.out.print(f + 1 + " ");
else
System.out.print(-1 + " ");
}
}
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, 3, 2, 4, 6 };
int[][] Q
= { { 2, 5 }, { 1, 3, 5 }, { 2, 4 }, { 2, 8 } };
int N = arr.length;
PerformQueries(arr, N, Q);
}
}
// This code is contributed by hemanthsawarna1506
Python3
# Python3 program to implement
# the above approach
import math
# Function to find the mid
# of start and end
def getMid(s,e):
return s + math.floor((e - s) / 2)
def updateValue(arr,st,ss,se,index,value,node):
# If index is out of range
if (index < ss or index > se):
print("Invalid Input")
return
# If a leaf node is found
if (ss == se):
# update value in array
arr[index] = value
# Update value in
# the segment tree
st[node] = value
else:
# Stores mid of ss and se
mid = getMid(ss, se)
# If index is less than or
# equal to mid
if (index >= ss and index <= mid):
# Recursively call for left subtree
updateValue(arr, st, ss, mid, index, value, 2 * node + 1)
else:
# Recursively call for right subtree
updateValue(arr, st, mid + 1, se, index, value, 2 * node + 2)
# Update st[node]
st[node] = max(st[2 * node + 1], st[2 * node + 2])
# Function to find the position of first element
# which is greater than or equal to X
def findMinimumIndex(st, ss, se, K, si):
# If no such element found in current
# subtree which is greater than or
# equal to K
if (st[si] < K):
return 1000000000
# If current node is leaf node
if (ss == se):
# If value of current node
# is greater than or equal to X
if (st[si] >= K):
return ss
return 1000000000
# Stores mid of ss and se
mid = getMid(ss, se)
l = 1000000000
# If root of left subtree is
# greater than or equal to K
if (st[2 * si + 1] >= K):
l = min(l, findMinimumIndex(st, ss, mid, K, 2 * si + 1))
# If no such array element is
# found in the left subtree
if (l == 1e9 and st[2 * si + 2] >= K):
l = min(l, findMinimumIndex(st, mid + 1, se, K, 2 * si + 2))
return l
# Function to build a segment tree
def Build(arr, ss, se, st, si):
# If current node is leaf node
if (ss == se):
st[si] = arr[ss]
return arr[ss]
# store mid of ss and se
mid = getMid(ss, se)
# Stores maximum of left subtree and rightsubtree
st[si] = max(Build(arr, ss, mid, st, si * 2 + 1), Build(arr, mid + 1, se, st, si * 2 + 2))
return st[si]
# Function to initialize a segment tree
# for the given array
def constructST(arr,n):
# Height of segment tree
x = math.ceil(math.log(n) / math.log(2))
# Maximum size of segment tree
max_size = 2 * pow(2, x) - 1
# Allocate memory
st = [0]*(max_size)
# Fill the allocated memory st
Build(arr, 0, n - 1, st, 0)
# Return the constructed segment tree
return st
def PerformQueries(arr, N, Q):
# Build segment tree for the given array
st = constructST(arr, N)
# Traverse the query array
for i in range(len(Q)):
# If query of type 1 found
if (Q[i][0] == 1):
updateValue(arr, st, 0, N - 1, Q[i][1] - 1, 5, 0)
else:
# Stores index of first array element
# which is greater than or equal
# to Q[i][1]
f = findMinimumIndex(st, 0, N - 1, Q[i][1], 0)
if (f < N):
print((f + 1 ), end = " ")
else:
print(-1, end = " ")
# Driver code
arr = [1, 3, 2, 4, 6 ]
Q= [[ 2, 5 ], [ 1, 3, 5 ], [2, 4 ], [ 2, 8 ]]
N = len(arr)
PerformQueries(arr, N, Q)
# This code is contributed by decode2207.
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to find the mid
// of start and end
static int getMid(int s, int e)
{
return s + (e - s) / 2;
}
static void updateValue(int[] arr, int[] st, int ss,
int se, int index, int value,
int node)
{
// If index is out of range
if (index < ss || index > se)
{
Console.WriteLine("Invalid Input");
return;
}
// If a leaf node is found
if (ss == se)
{
// Update value in array
arr[index] = value;
// Update value in
// the segment tree
st[node] = value;
}
else
{
// Stores mid of ss and se
int mid = getMid(ss, se);
// If index is less than or
// equal to mid
if (index >= ss && index <= mid)
{
// Recursively call for left subtree
updateValue(arr, st, ss, mid, index, value,
2 * node + 1);
}
else
{
// Recursively call for right subtree
updateValue(arr, st, mid + 1, se, index,
value, 2 * node + 2);
}
// Update st[node]
st[node] = Math.Max(st[2 * node + 1],
st[2 * node + 2]);
}
}
// Function to find the position of first element
// which is greater than or equal to X
static int findMinimumIndex(int[] st, int ss, int se,
int K, int si)
{
// If no such element found in current
// subtree which is greater than or
// equal to K
if (st[si] < K)
return 1000000000;
// If current node is leaf node
if (ss == se)
{
// If value of current node
// is greater than or equal to X
if (st[si] >= K)
{
return ss;
}
return 1000000000;
}
// Stores mid of ss and se
int mid = getMid(ss, se);
int l = 1000000000;
// If root of left subtree is
// greater than or equal to K
if (st[2 * si + 1] >= K)
l = Math.Min(l, findMinimumIndex(st, ss, mid, K,
2 * si + 1));
// If no such array element is
// found in the left subtree
if (l == 1e9 && st[2 * si + 2] >= K)
l = Math.Min(l,
findMinimumIndex(st, mid + 1, se,
K, 2 * si + 2));
return l;
}
// Function to build a segment tree
static int Build(int[] arr, int ss, int se,
int[] st, int si)
{
// If current node is leaf node
if (ss == se)
{
st[si] = arr[ss];
return arr[ss];
}
// Store mid of ss and se
int mid = getMid(ss, se);
// Stores maximum of left subtree and rightsubtree
st[si] = Math.Max(
Build(arr, ss, mid, st, si * 2 + 1),
Build(arr, mid + 1, se, st, si * 2 + 2));
return st[si];
}
// Function to initialize a segment tree
// for the given array
static int[] constructST(int[] arr, int n)
{
// Height of segment tree
int x = (int)Math.Ceiling(Math.Log(n) /
Math.Log(2));
// Maximum size of segment tree
int max_size = 2 * (int)Math.Pow(2, x) - 1;
// Allocate memory
int[] st = new int[max_size];
// Fill the allocated memory st
Build(arr, 0, n - 1, st, 0);
// Return the constructed segment tree
return st;
}
static void PerformQueries(int[] arr, int N, int[][] Q)
{
// Build segment tree for the given array
int[] st = constructST(arr, N);
// Traverse the query array
for(int i = 0; i < Q.Length; i++)
{
// If query of type 1 found
if (Q[i][0] == 1)
updateValue(arr, st, 0, N - 1,
Q[i][1] - 1, 5, 0);
else
{
// Stores index of first array element
// which is greater than or equal
// to Q[i][1]
int f = findMinimumIndex(st, 0, N - 1,
Q[i][1], 0);
if (f < N)
Console.Write(f + 1 + " ");
else
Console.Write(-1 + " ");
}
}
}
// Driver Code
public static void Main(string[] args)
{
int[] arr = { 1, 3, 2, 4, 6 };
int[][] Q = new int[4][];
// Initialize the elements
Q[0] = new int[] { 2, 5 };
Q[1] = new int[] { 1, 3, 5 };
Q[2] = new int[] { 2, 4 };
Q[3] = new int[] { 2, 8 };
int N = arr.Length;
PerformQueries(arr, N, Q);
}
}
// This code is contributed by ukasp
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to find the mid
// of start and end
function getMid(s,e)
{
return s + Math.floor((e - s) / 2);
}
function updateValue(arr,st,ss,se,index,value,node)
{
// If index is out of range
if (index < ss || index > se)
{
document.write("Invalid Input<br>");
return;
}
// If a leaf node is found
if (ss == se)
{
// update value in array
arr[index] = value;
// Update value in
// the segment tree
st[node] = value;
}
else
{
// Stores mid of ss and se
let mid = getMid(ss, se);
// If index is less than or
// equal to mid
if (index >= ss && index <= mid)
{
// Recursively call for left subtree
updateValue(arr, st, ss, mid, index, value,
2 * node + 1);
}
else
{
// Recursively call for right subtree
updateValue(arr, st, mid + 1, se, index,
value, 2 * node + 2);
}
// Update st[node]
st[node] = Math.max(st[2 * node + 1],
st[2 * node + 2]);
}
}
// Function to find the position of first element
// which is greater than or equal to X
function findMinimumIndex(st,ss,se,K,si)
{
// If no such element found in current
// subtree which is greater than or
// equal to K
if (st[si] < K)
return 1000000000;
// If current node is leaf node
if (ss == se)
{
// If value of current node
// is greater than or equal to X
if (st[si] >= K)
{
return ss;
}
return 1000000000;
}
// Stores mid of ss and se
let mid = getMid(ss, se);
let l = 1000000000;
// If root of left subtree is
// greater than or equal to K
if (st[2 * si + 1] >= K)
l = Math.min(l, findMinimumIndex(st, ss, mid, K,
2 * si + 1));
// If no such array element is
// found in the left subtree
if (l == 1e9 && st[2 * si + 2] >= K)
l = Math.min(l,
findMinimumIndex(st, mid + 1, se,
K, 2 * si + 2));
return l;
}
// Function to build a segment tree
function Build(arr,ss,se,st,si)
{
// If current node is leaf node
if (ss == se)
{
st[si] = arr[ss];
return arr[ss];
}
// store mid of ss and se
let mid = getMid(ss, se);
// Stores maximum of left subtree and rightsubtree
st[si] = Math.max(
Build(arr, ss, mid, st, si * 2 + 1),
Build(arr, mid + 1, se, st, si * 2 + 2));
return st[si];
}
// Function to initialize a segment tree
// for the given array
function constructST(arr,n)
{
// Height of segment tree
let x = Math.ceil(Math.log(n) / Math.log(2));
// Maximum size of segment tree
let max_size = 2 * Math.pow(2, x) - 1;
// Allocate memory
let st = new Array(max_size);
// Fill the allocated memory st
Build(arr, 0, n - 1, st, 0);
// Return the constructed segment tree
return st;
}
function PerformQueries(arr,N,Q)
{
// Build segment tree for the given array
let st = constructST(arr, N);
// Traverse the query array
for (let i = 0; i < Q.length; i++)
{
// If query of type 1 found
if (Q[i][0] == 1)
updateValue(arr, st, 0, N - 1, Q[i][1] - 1,
5, 0);
else {
// Stores index of first array element
// which is greater than or equal
// to Q[i][1]
let f = findMinimumIndex(st, 0, N - 1,
Q[i][1], 0);
if (f < N)
document.write((f + 1 )+ " ");
else
document.write(-1 + " ");
}
}
}
// Driver Code
let arr=[1, 3, 2, 4, 6 ];
let Q= [[ 2, 5 ], [ 1, 3, 5 ], [2, 4 ], [ 2, 8 ]];
let N = arr.length;
PerformQueries(arr, N, Q);
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
5 3 -1
Publicación traducida automáticamente
Artículo escrito por kapil16garg y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA