Запрос, чтобы проверить, состоит ли диапазон из последовательных элементов

Опубликовано: 5 Января, 2022

Учитывая массив из n непоследовательных целых чисел и Q запросов, задача состоит в том, чтобы проверить, являются ли элементы для данного диапазона l и r последовательными или нет.

Примеры:

Input: arr = { 2, 4, 3, 7, 6, 1}, Q = { (1, 3), (3, 5), (5, 6) }
Output: Yes, No, No
Explanation: Array elements from (1, 3) = {2, 4, 3}, (3, 5) = {3, 7, 6}, (5, 6) = {6, 1}
So the answer is Yes, No, No
Input: arr = {1, 2, 3, 4, 5}, Q = { (1, 2), (4, 5), (1, 5) }
Output:Yes, Yes, Yes

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Наивный подход:
Подмассив между диапазоном l и r можно отсортировать и проверить, содержит ли он последовательные элементы или нет.

Сложность времени: O (q * n * log n)
где n - размер массива, q - количество запросов.

Эффективный подход:

Сегментное дерево можно использовать для получения минимума и максимума в диапазоне.
Если минимальный элемент подмассива равен x, а максимальный - y, тогда мы можем не иметь элемента меньше x и больше чем y, поэтому мы можем сказать, что x <= arr [i] <= y .
Поскольку нет повторяющихся элементов, можно сделать вывод, что если разность максимального и минимального элемента + 1 равна длине диапазона (r-l + 1), то диапазон состоит из последовательных элементов.

Ниже представлена реализация описанного выше подхода.

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" ) << "
" ;
    }
 
    return 0;
 }

Джава

 // 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" ) + "
" );
        }
    }
 }
 
// 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
                            
                    
                                            Technical Scripter
                                    
РЕКОМЕНДУЕМЫЕ СТАТЬИКоличество чисел между L и R, взаимно простых с P
27 Февраля, 2023
Постройте матрицу, каждая строка и столбец которой содержат N и M единиц соответственно.
27 Февраля, 2023
Максимизируйте сумму трех чисел, выполнив побитовое XOR
27 Февраля, 2023
Проверьте, совпадает ли набор первых элементов X одного массива с набором первых элементов Y другого
27 Февраля, 2023
Подсчитать подстроки нечетной длины с медианой, такой же, как K-й символ строки
27 Февраля, 2023
Найти лексикографически первый идентификатор каждого домена из заданного массива идентификаторов электронной почты
27 Февраля, 2023
Найдите общее количество фигур 'X'
26 Февраля, 2023
Максимальное значение узла, которое может быть достигнуто с использованием данных соединений
26 Февраля, 2023

    


        
                    < PROGLER >

                

                    Общее
Контакты
Политика конфиденциальности

                    Обучение
Блог

                

                © progler.ru 2024. Все права защищены.
            

    