Проверьте, образуют ли элементы массива в данном диапазоне перестановку, выполнив заданные обновления.

Дан массив arr[] , состоящий из N различных целых чисел, и двумерный массив Q[][3] , состоящий из M запросов двух типов, операции которых следующие:

• [1, P, X] обновить позицию P с помощью X .
• [2, L, R] проверить, образуют ли элементы массива в диапазоне [L, R] перестановку или нет.

Для каждого запроса второго типа найти, образует ли диапазон [L, R] перестановку или нет

Примеры :

Input: arr[] = {6, 4, 1, 2, 3, 8, 10}, Q[][] = {{2, 2, 4}, {1, 2, 9}, {2, 2, 4}, {1, 2, 1}, {2, 0, 4}, {1, 0, 5}, {2, 0, 4}}
Output: 
YES
NO
NO
YES

Explanation: 
Query 1: This is Query Type 2. The elements of the array over the range [2, 4] are {1, 2, 3} which forms a permutation. Hence, print “YES”.
Query 2: This is Query Type 1. [2, 9] We Update index 2 with 9 now arr[] becomes {6, 4, 9, 2, 3, 8, 10}.
Query 3: This is Query Type 2. The elements of the array over the range [2, 4] are [9, 2, 3] which does not forms a permutation. Hence, Print “NO”
Query 4: This is Query Type 1. [2, 1] We Update index 2 with 1 now arr[] becomes {6, 4, 1, 2, 3, 8, 10}.
Query 5: This is Query Type 2. The elements of the array over the range [0, 4] are [6, 4, 1, 2, 3] which does not forms a permutation. Hence, Print “NO”
Query 6: This is Query Type 1. [0, 5] We Update index 0 with 5 now arr[] becomes {5, 4, 1, 2, 3, 8, 10}.
Query 7: This is Query Type 2. The elements of the array over the range [0, 4] are {5, 4, 1, 2, 3} which forms a permutation. Hence, print “YES”.

Input: arr[] = {1, 2, 4, 3, 9}, Q[][] = {{2, 0, 3}, {1, 0, 5}, {2, 0, 3}}
Output: 
YES
NO

Наивный подход: основной способ решения проблемы заключается в следующем:

Each query of type 1 can be handled in constant time just by updating respective index. For queries of second type, Traverse the given array over the range [L, R] and check if every element is present or not from 1 to R – L + 1. This can be done by taking the sum of all elements from L to R if it is equal to the sum of 1 + 2 + 3 + 4 + . . . . + size of subarray [L, R], then print “YES”. Otherwise, print “NO”.

Временная сложность: O(N * M)
Вспомогательное пространство: O(1)

Эффективный подход. Описанный выше подход можно оптимизировать с помощью дерева сегментов , основанного на следующей идее:

The idea is rather than calculating the sum of elements from L to R for each query we can maintain answer for every range from L to R using Segment Tree. For Each query of type 2, sum from L to R can be found in O(log n) time by using the segment tree. Query of type 1 can be handled using segment tree in O(logn) per query.

The sum from 1 + 2 + 3 + 4 + . . . + size of subarray [L, R] can be found using the number theory formula for finding the sum of the first n natural numbers which is n * (n + 1) / 2. 

Выполните следующие шаги, чтобы решить проблему:

• Построить дерево сегментов для данного массива arr[] за O(N * logN) .
• Пройти заданный массив запросов Q[][]
• Для запроса типа 1 вызовите функцию updateValue и передайте pos (положение) и значение .
• Для каждого запроса второго типа инициируйте переменную size размером подмассива [L, R] .
• Инициируйте переменную total_From_1_To_Size с помощью n * ( n + 1) / 2.
• Инициализируйте переменную total_From_L_To_R и получите значение из дерева сегментов.
• Если total_From_L_To_R и total_From_1_To_Size равны, то выведите «YES» , иначе выведите «NO» .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N*logN + M*logN)
Вспомогательное пространство: O(N)

Статьи по Теме:

• Введение в массивы - учебные пособия по структурам данных и алгоритмам
• Дерево сегментов