Consulta para comprobar si un rango está formado por elementos consecutivos

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: 
 

  1. Se puede usar un árbol de segmentos para obtener el mínimo y el máximo en un rango.
  2. 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 .
  3. 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *