Dada una array de n enteros no consecutivos y Q consultas, la tarea es verificar si para el rango l y r dado , los elementos son consecutivos o no.
Ejemplos:
Entrada: arr = { 2, 4, 3, 7, 6, 1}, Q = { (1, 3), (3, 5), (5, 6) }
Salida: Sí, No, No
Explicación: Elementos de array de (1, 3) = {2, 4, 3}, (3, 5) = {3, 7, 6}, (5, 6) = {6, 1}
Entonces la respuesta es Sí, No, No
Entrada : arr = {1, 2, 3, 4, 5}, Q = { (1, 2), (4, 5), (1, 5) }
Salida: Sí, Sí, Sí
Enfoque ingenuo:
la array secundaria entre el rango l y r se puede ordenar y verificar si contiene elementos consecutivos o no.
Complejidad de tiempo: O(q*n*log n)
donde n es el tamaño de la array y q es el número de consultas.
Enfoque eficiente:
- Se puede usar un árbol de segmentos para obtener el mínimo y el máximo en un rango.
- Si el elemento mínimo de un subarreglo es x y el elemento máximo es y, entonces podemos que no haya ningún elemento menor que x y mayor que y, por lo que podemos decir que x<=arr[i]<=y .
- Como no hay elementos repetidos, se puede concluir que si la diferencia del elemento máximo y mínimo + 1 es igual a la longitud del rango (r-l+1), entonces el rango consta de elementos consecutivos.
A continuación se muestra la implementación del enfoque anterior.
CPP
// C++ implementation of the above approach.
#include <bits/stdc++.h>
using namespace std;
// Segment tree
int tree_min[1000001],
tree_max[1000001];
// Functions to return
// minimum and maximum
int min(int a, int b)
{
return a < b ? a : b;
}
int max(int a, int b)
{
return a > b ? a : b;
}
// Segment tree for minimum element
void build_min(int array[], int node,
int left, int right)
{
// If left is equal to right
if (left == right)
tree_min[node] = array[left];
else {
// Divide the segment into equal halves
build_min(array, 2 * node, left,
(left + right) / 2);
build_min(array, 2 * node + 1,
(left + right) / 2 + 1, right);
// Update the element as minimum
// of the divided two subarrays
tree_min[node] = min(tree_min[2 * node],
tree_min[2 * node + 1]);
}
}
// Query to find a minimum
// in a given ranges
int query_min(int node, int c_l,
int c_r, int l, int r)
{
// Out of range
if (c_l > r || c_r < l)
return 1e9;
// Within the range completely
if (c_l >= l && c_r <= r)
return tree_min[node];
else
// Divide the range into two halves
// Query for each half
// and return the minimum of two
return min(query_min(2 * node, c_l,
(c_l + c_r) / 2, l, r),
query_min(2 * node + 1,
(c_l + c_r) / 2 + 1,
c_r, l, r));
}
// Segment tree for maximum element
void build_max(int array[], int node,
int left, int right)
{
// If left is equal to right
if (left == right)
tree_max[node] = array[left];
else {
// Divide the segment into equal halves
build_max(array, 2 * node, left,
(left + right) / 2);
build_max(array, 2 * node + 1,
(left + right) / 2 + 1, right);
// Update the element as maximum
// of the divided two subarrays
tree_max[node] = max(tree_max[2 * node],
tree_max[2 * node + 1]);
}
}
// Query to find maximum
// in a given ranges
int query_max(int node, int c_l,
int c_r, int l, int r)
{
// Out of range
if (c_l > r || c_r < l)
return -1;
// Within the range completely
if (c_l >= l && c_r <= r)
return tree_max[node];
else
// Divide the range into two halves
// and query for each half
// and return the maximum of two
return max(query_max(2 * node, c_l,
(c_l + c_r) / 2, l, r),
query_max(2 * node + 1,
(c_l + c_r) / 2 + 1,
c_r, l, r));
}
// Build the tree
void init(int array[], int n)
{
build_min(array, 1, 0, n - 1);
build_max(array, 1, 0, n - 1);
}
// Check if the given range is Consecutive
bool isConsecutive(int x, int y, int n)
{
return ((query_max(1, 0, n - 1, x, y)
- query_min(1, 0, n - 1, x, y))
== (y - x));
}
// Driver code
int main()
{
int arr[] = { 2, 4, 3, 7, 6, 1 };
int query[][2] = { { 1, 3 }, { 3, 5 }, { 5, 6 } };
int n = sizeof(arr) / sizeof(int), q = 3;
init(arr, n);
for (int i = 0; i < q; i++) {
int l, r;
l = query[i][0];
r = query[i][1];
cout << (isConsecutive(l - 1, r - 1, n) ?
"Yes" : "No") << "\n";
}
return 0;
}
Java
// Java implementation of the above approach.
class GFG
{
// Segment tree
static int[] tree_min = new int[1000001];
static int[] tree_max = new int[1000001];
// Functions to return
// minimum and maximum
static int min(int a, int b)
{
return a < b ? a : b;
}
static int max(int a, int b)
{
return a > b ? a : b;
}
// Segment tree for minimum element
static void build_min(int array[], int node, int left, int right)
{
// If left is equal to right
if (left == right)
tree_min[node] = array[left];
else
{
// Divide the segment into equal halves
build_min(array, 2 * node, left, (left + right) / 2);
build_min(array, 2 * node + 1,
(left + right) / 2 + 1, right);
// Update the element as minimum
// of the divided two subarrays
tree_min[node] = Math.min(tree_min[2 * node],
tree_min[2 * node + 1]);
}
}
// Query to find a minimum
// in a given ranges
static int query_min(int node, int c_l, int c_r, int l, int r)
{
// Out of range
if (c_l > r || c_r < l)
return (int) 1e9;
// Within the range completely
if (c_l >= l && c_r <= r)
return tree_min[node];
else
// Divide the range into two halves
// Query for each half
// and return the minimum of two
return min(query_min(2 * node, c_l, (c_l + c_r) / 2, l, r),
query_min(2 * node + 1, (c_l + c_r) / 2 + 1, c_r, l, r));
}
// Segment tree for maximum element
static void build_max(int array[], int node, int left, int right)
{
// If left is equal to right
if (left == right)
tree_max[node] = array[left];
else
{
// Divide the segment into equal halves
build_max(array, 2 * node, left, (left + right) / 2);
build_max(array, 2 * node + 1, (left + right) / 2 + 1, right);
// Update the element as maximum
// of the divided two subarrays
tree_max[node] = Math.max(tree_max[2 * node],
tree_max[2 * node + 1]);
}
}
// Query to find maximum
// in a given ranges
static int query_max(int node, int c_l, int c_r, int l, int r)
{
// Out of range
if (c_l > r || c_r < l)
return -1;
// Within the range completely
if (c_l >= l && c_r <= r)
return tree_max[node];
else
// Divide the range into two halves
// and query for each half
// and return the maximum of two
return Math.max(query_max(2 * node, c_l, (c_l + c_r) / 2, l, r),
query_max(2 * node + 1, (c_l + c_r) / 2 + 1, c_r, l, r));
}
// Build the tree
static void init(int array[], int n)
{
build_min(array, 1, 0, n - 1);
build_max(array, 1, 0, n - 1);
}
// Check if the given range is Consecutive
static boolean isConsecutive(int x, int y, int n)
{
return ((query_max(1, 0, n - 1, x, y) -
query_min(1, 0, n - 1, x, y)) == (y - x));
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 2, 4, 3, 7, 6, 1 };
int query[][] = { { 1, 3 }, { 3, 5 }, { 5, 6 } };
int n = arr.length, q = 3;
init(arr, n);
for (int i = 0; i < q; i++)
{
int l, r;
l = query[i][0];
r = query[i][1];
System.out.print((isConsecutive(l - 1, r - 1, n) ?
"Yes" : "No") + "\n");
}
}
}
// This code is contributed by PrinciRaj1992
Python
# Python3 implementation of the above approach.
# Segment tree
tree_min = [0] * 1000001
tree_max = [0] * 1000001
# Segment tree for minimum element
def build_min(array, node,left, right):
# If left is equal to right
if (left == right):
tree_min[node] = array[left]
else :
# Divide the segment into equal halves
build_min(array, 2 * node, left,(left + right) // 2)
build_min(array, 2 * node + 1,(left + right) // 2 + 1, right)
# Update the element as minimum
# of the divided two subarrays
tree_min[node] = min(tree_min[2 * node], tree_min[2 * node + 1])
# Query to find a minimum
# in a given ranges
def query_min(node, c_l, c_r, l, r):
# Out of range
if (c_l > r or c_r < l):
return 10**9
# Within the range completely
if (c_l >= l and c_r <= r):
return tree_min[node]
else:
# Divide the range into two halves
# Query for each half
# and return the minimum of two
return min(query_min(2 * node, c_l,(c_l + c_r) // 2, l, r),
query_min(2 * node + 1, (c_l + c_r) // 2 + 1,c_r, l, r))
# Segment tree for maximum element
def build_max(array, node, left, right):
# If left is equal to right
if (left == right):
tree_max[node] = array[left]
else :
# Divide the segment into equal halves
build_max(array, 2 * node, left,(left + right) // 2)
build_max(array, 2 * node + 1,(left + right) // 2 + 1, right)
# Update the element as maximum
# of the divided two subarrays
tree_max[node] = max(tree_max[2 * node],tree_max[2 * node + 1])
# Query to find maximum
# in a given ranges
def query_max(node, c_l, c_r, l, r):
# Out of range
if (c_l > r or c_r < l):
return -1
# Within the range completely
if (c_l >= l and c_r <= r):
return tree_max[node]
else:
# Divide the range into two halves
# and query for each half
# and return the maximum of two
return max(query_max(2 * node, c_l,(c_l + c_r) // 2, l, r),query_max(2 * node + 1,(c_l + c_r) // 2 + 1,c_r, l, r))
# Build the tree
def init(array, n):
build_min(array, 1, 0, n - 1)
build_max(array, 1, 0, n - 1)
# Check if the given range is Consecutive
def isConsecutive(x, y, n):
return ((query_max(1, 0, n - 1, x, y) - query_min(1, 0, n - 1, x, y)) == (y - x))
# Driver code
arr = [2, 4, 3, 7, 6, 1]
query = [ [1, 3] , [3, 5 ], [5, 6] ]
n = len(arr)
q = 3
init(arr, n)
for i in range(q):
l = query[i][0]
r = query[i][1]
if (isConsecutive(l - 1, r - 1, n) ):
print("Yes")
else:
print("No")
# This code is contributed by mohit kumar 29
C#
// C# implementation of the above approach.
using System;
class GFG
{
// Segment tree
static int[] tree_min = new int[1000001];
static int[] tree_max = new int[1000001];
// Functions to return
// minimum and maximum
static int min(int a, int b)
{
return a < b ? a : b;
}
static int max(int a, int b)
{
return a > b ? a : b;
}
// Segment tree for minimum element
static void build_min(int []array, int node,
int left, int right)
{
// If left is equal to right
if (left == right)
tree_min[node] = array[left];
else
{
// Divide the segment into equal halves
build_min(array, 2 * node, left, (left + right) / 2);
build_min(array, 2 * node + 1,
(left + right) / 2 + 1, right);
// Update the element as minimum
// of the divided two subarrays
tree_min[node] = Math.Min(tree_min[2 * node],
tree_min[2 * node + 1]);
}
}
// Query to find a minimum
// in a given ranges
static int query_min(int node, int c_l,
int c_r, int l, int r)
{
// Out of range
if (c_l > r || c_r < l)
return (int) 1e9;
// Within the range completely
if (c_l >= l && c_r <= r)
return tree_min[node];
else
// Divide the range into two halves
// Query for each half
// and return the minimum of two
return min(query_min(2 * node, c_l,
(c_l + c_r) / 2, l, r),
query_min(2 * node + 1,
(c_l + c_r) / 2 + 1, c_r, l, r));
}
// Segment tree for maximum element
static void build_max(int []array, int node,
int left, int right)
{
// If left is equal to right
if (left == right)
tree_max[node] = array[left];
else
{
// Divide the segment into equal halves
build_max(array, 2 * node, left, (left + right) / 2);
build_max(array, 2 * node + 1, (left + right) / 2 + 1, right);
// Update the element as maximum
// of the divided two subarrays
tree_max[node] = Math.Max(tree_max[2 * node],
tree_max[2 * node + 1]);
}
}
// Query to find maximum
// in a given ranges
static int query_max(int node, int c_l,
int c_r, int l, int r)
{
// Out of range
if (c_l > r || c_r < l)
return -1;
// Within the range completely
if (c_l >= l && c_r <= r)
return tree_max[node];
else
// Divide the range into two halves
// and query for each half
// and return the maximum of two
return Math.Max(query_max(2 * node, c_l,
(c_l + c_r) / 2, l, r),
query_max(2 * node + 1,
(c_l + c_r) / 2 + 1, c_r, l, r));
}
// Build the tree
static void init(int []array, int n)
{
build_min(array, 1, 0, n - 1);
build_max(array, 1, 0, n - 1);
}
// Check if the given range is Consecutive
static bool isConsecutive(int x, int y, int n)
{
return ((query_max(1, 0, n - 1, x, y) -
query_min(1, 0, n - 1, x, y)) == (y - x));
}
// Driver code
public static void Main(String[] args)
{
int []arr = {2, 4, 3, 7, 6, 1};
int [,]query = {{ 1, 3 }, { 3, 5 }, { 5, 6 }};
int n = arr.Length, q = 3;
init(arr, n);
for (int i = 0; i < q; i++)
{
int l, r;
l = query[i,0];
r = query[i,1];
Console.Write((isConsecutive(l - 1, r - 1, n) ?
"Yes" : "No") + "\n");
}
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript implementation of the above approach.
// Segment tree
let tree_min = new Array(1000001);
let tree_max = new Array(1000001);
// Functions to return
// minimum and maximum
function min(a,b)
{
return a < b ? a : b;
}
function max(a,b)
{
return a > b ? a : b;
}
// Segment tree for minimum element
function build_min(array,node,left,right)
{
// If left is equal to right
if (left == right)
tree_min[node] = array[left];
else
{
// Divide the segment into equal halves
build_min(array, 2 * node, left,
Math.floor((left + right) / 2));
build_min(array, 2 * node + 1,
Math.floor((left + right) / 2) + 1, right);
// Update the element as minimum
// of the divided two subarrays
tree_min[node] = Math.min(tree_min[2 * node],
tree_min[2 * node + 1]);
}
}
// Query to find a minimum
// in a given ranges
function query_min(node,c_l,c_r,l,r)
{
// Out of range
if (c_l > r || c_r < l)
return 1e9;
// Within the range completely
if (c_l >= l && c_r <= r)
return tree_min[node];
else
// Divide the range into two halves
// Query for each half
// and return the minimum of two
return min(query_min(2 * node, c_l,
Math.floor((c_l + c_r) / 2), l, r),
query_min(2 * node + 1,
Math.floor((c_l + c_r) / 2) + 1, c_r, l, r));
}
// Segment tree for maximum element
function build_max(array,node,left,right)
{
// If left is equal to right
if (left == right)
tree_max[node] = array[left];
else
{
// Divide the segment into equal halves
build_max(array, 2 * node, left,
Math.floor((left + right) / 2));
build_max(array, 2 * node + 1,
Math.floor((left + right) / 2) + 1, right);
// Update the element as maximum
// of the divided two subarrays
tree_max[node] = Math.max(tree_max[2 * node],
tree_max[2 * node + 1]);
}
}
// Query to find maximum
// in a given ranges
function query_max(node,c_l,c_r,l,r)
{
// Out of range
if (c_l > r || c_r < l)
return -1;
// Within the range completely
if (c_l >= l && c_r <= r)
return tree_max[node];
else
// Divide the range into two halves
// and query for each half
// and return the maximum of two
return Math.max(query_max(2 * node, c_l,
Math.floor((c_l + c_r) / 2), l, r),
query_max(2 * node + 1,
Math.floor((c_l + c_r) / 2) + 1, c_r, l, r));
}
// Build the tree
function init(array,n)
{
build_min(array, 1, 0, n - 1);
build_max(array, 1, 0, n - 1);
}
// Check if the given range is Consecutive
function isConsecutive(x,y,n)
{
return ((query_max(1, 0, n - 1, x, y) -
query_min(1, 0, n - 1, x, y)) == (y - x));
}
// Driver code
let arr=[ 2, 4, 3, 7, 6, 1];
let query=[[ 1, 3 ], [ 3, 5 ], [ 5, 6 ] ];
let n = arr.length, q = 3;
init(arr, n);
for (let i = 0; i < q; i++)
{
let l, r;
l = query[i][0];
r = query[i][1];
document.write((isConsecutive(l - 1, r - 1, n) ?
"Yes" : "No") + "<br>");
}
// This code is contributed by patel2127
</script>
Producción:
Yes No No
Complejidad del tiempo: O(Q*log(n))
Publicación traducida automáticamente
Artículo escrito por andrew1234 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA