Подсчитайте способы сделать заданный подмассив строго возрастающим, заменив один элемент для Q запросов

Опубликовано: 25 Февраля, 2023

Дан строго возрастающий массив A[] размера N , целое число K и Q запросов типа [L, R] , задача состоит в том, чтобы посчитать количество способов, при которых подмассив из L в R остается строго возрастающим при единственной замене выполняется, и все элементы будут в диапазоне [1, K] .

Примеры:

Input: A[] = {1, 2, 4, 5}, K = 5, Q = 2, Queries[][] = {{1, 2}, {2, 3}}
Output: 4 3
Explanation: For Query1 – subarray [2, 4]. 
The ways will be [1, 4] [3, 4] (only 1st position is replaced), and 
[2, 3] [2, 5] (only 2nd position is changed). So number of ways are 4.
For Query2 – subarray [4, 5]. 
The ways are  [1, 5] [2, 5] [3, 5] (only 1st position is replaced). 
Second position cannot be replaced as is already 5 which is equal to K 
and the previous element is 4. There does not exist any element in between. 
So number of ways are 3.

Input: A[] = {1, 3, 4}, K = 4, Q = 1, Queries = {{0, 2}}
Output: 2

Подход: Задача может быть решена на основе следующей идеи:

We need to calculate the possible changes for every element in each query so here pre-computed values can save an extra iteration of N for each query separately and each query can be answered in O(1) using the precomputed values in prefix sum.

Выполните следующие шаги, чтобы ответить на каждый запрос за постоянное время.

  • Предварительно вычислите, что если i- й элемент заменен, то сколько существует возможностей, и сохраните его в массиве (скажем , pre [ ] ).
  • A[i] можно заменить всеми элементами диапазона (A[i-1], A[i+1]), кроме самого A[i] . Итак, количество способов = A[i+1] – A[i-1] – 2 .
  • Вычислите сумму префиксов в pre[] для хранения количества возможных путей, где pre[i] обозначает возможные пути от 0 до i .
  • Теперь, используя массив суммы префиксов, мы можем ответить на каждый запрос, используя pre [R] – pre[L – 1] .
    • Но можно заменить элемент с индексом L элементами от 1 до a[L + 1] – 1 и элемент с индексом R от a[R] + 1 до K , поскольку подмассив от L до R должен быть отсортирован путем замены ровно одного элемента.
    • Поэтому добавьте A[L + 1] – 2 для позиции L.
    • Точно так же для последнего элемента добавьте (K – (A[R – 1] + 1)), так как элемент в позиции R может начинаться с A[R – 1] + 1 и идти до K .
  • Затем добавьте все эти разные части и верните окончательный ответ.

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

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

РЕКОМЕНДУЕМЫЕ СТАТЬИ