Максимум (Розбір)

Задача вимагає відповідати на запити максимуму на відрізку. Елементи масиву не змінюються, тому підходить статична структура даних. Кількість запитів сягає $5 \cdot 1 0^{5}$ 5 \cdot 10^5, а довжина масиву — $1 0^{5}$ 10^5. Обчислення максимуму на кожному відрізку напряму вимагатиме до $5 \cdot 1 0^{10}$ 5 \cdot 10^{10} операцій, що занадто повільно.

Використаємо sparse table (розріджену таблицю) для задачі RMQ, але замість мінімуму шукатимемо максимум (Range Maximum Query). Максимум, як і мінімум, не змінюється, якщо певний елемент порахувати двічі. Тому відрізок запиту можна покрити двома відрізками довжини $2^{k}$ 2^k, що перекриваються, і вибрати більший з їхніх максимумів.

Клітинка таблиці може зберігати або індекс максимального елемента, або сам максимум. За умовою задачі потрібно виводити лише значення, тому достатньо зберігати максимум. Варіант з індексом потрібен, коли треба знати позицію максимуму. Нижче наведено обидві реалізації.

За умовою задачі $1 \leq l, r \leq n$ 1 \le l, r \le n, і не гарантується, що $l \leq r$ l \le r. Тому перед виконанням запиту, за потреби, межі міняємо місцями.

Складність. Побудова розрідженої таблиці займає $O (n lo g n)$ O(n \log n), а кожен запит — $O (1)$ . Загальна складність — $O (n lo g n + q)$ O(n \log n + q).

Приклад

Розглянемо масив з прикладу: $(5, 1, 2, 8, 7, 6, 10, 7, 5, 6)$ (5, 1, 2, 8, 7, 6, 10, 7, 5, 6). Таблиця $ma s$ , у якій $ma s [i] [j]$ mas[i][j] — максимум на відрізку $[i; i + 2^{j} - 1]$ [i; i + 2^j - 1], наведена нижче. Прочерк означає, що відрізок виходить за межі масиву.

$j ∖ i$ \boldsymbol{j \setminus i}	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$
$0$	$5$	$1$	$2$	$8$	$7$	$6$	$10$	$7$	$5$	$6$
$1$	$5$	$2$	$8$	$8$	$7$	$10$	$10$	$7$	$6$	—
$2$	$8$	$8$	$8$	$10$	$10$	$10$	$10$	—	—	—
$3$	$10$	$10$	$10$	—	—	—	—	—	—	—

Наприклад, $ma s [4] [2] = max (ma s [4] [1], ma s [6] [1]) = max (8, 10) = 10$ mas[4][2] = \max(mas[4][1], mas[6][1]) = \max(8, 10) = 10 — це максимум на відрізку $[4; 7]$ .

Розглянемо запит $26$ . Довжина відрізка дорівнює $5$ , а найбільший степінь двійки, що не перевищує $5$ , дорівнює $4$ , тому $k = 2$ k = 2. Відрізок $[2; 6]$ покривається відрізками $[2; 5]$ та $[3; 6]$ , які перекриваються на відрізку $[3; 5]$ :

Відповідь дорівнює $max (ma s [2] [2], ma s [3] [2]) = max (8, 8) = 8$ \max(mas[2][2], mas[3][2]) = \max(8, 8) = 8. Елемент $8$ належить обом відрізкам, але це не впливає на значення максимуму.

Усі запити з прикладу наведено в таблиці:

запит	$k$	відрізки	максимуми	відповідь
$110$	$3$	$[1; 8]$ , $[3; 10]$	$10, 10$	$10$
$510$	$2$	$[5; 8]$ , $[7; 10]$	$10, 10$	$10$
$15$	$2$	$[1; 4]$ , $[2; 5]$	$8, 8$	$8$
$26$	$2$	$[2; 5]$ , $[3; 6]$	$8, 8$	$8$
$23$	$1$	$[2; 3]$ , $[2; 3]$	$2, 2$	$2$
$77$	$0$	$[7; 7]$ , $[7; 7]$	$10, 10$	$10$
$78$	$1$	$[7; 8]$ , $[7; 8]$	$10, 10$	$10$
$59$	$2$	$[5; 8]$ , $[6; 9]$	$10, 10$	$10$

Для відрізків довжини $1$ та $2$ (запити $23$ , $77$ та $78$ ) обидва покривальні відрізки збігаються з самим відрізком запиту.

Реалізація алгоритму — індекс максимуму

Вхідна послідовність $a_{i}$ a_i ( $n \leq 1 0^{5}$ n \le 10^5) зберігається в масиві $a$ , починаючи з індексу $1$ . У цьому варіанті клітинка $ma s [i] [j]$ mas[i][j] зберігає індекс максимального елемента на відрізку $[i; i + 2^{j} - 1]$ [i; i + 2^j - 1], а сам максимум дорівнює $a [ma s [i] [j]]$ a[mas[i][j]]. Оскільки $2^{16} \leq 1 0^{5} < 2^{17}$ 2^{16} \le 10^5 < 2^{17}, для другого виміру достатньо $L O GM A X = 17$ LOGMAX = 17.

#define MAX 100010
#define LOGMAX 17
int mas[MAX][LOGMAX];
int a[MAX];

Функція Build_RMQ_Array будує розріджену таблицю індексів.

void Build_RMQ_Array()
{

Для $j = 0$ j = 0 відрізок складається з одного елемента, тому $ma s [i] [0] = i$ mas[i][0] = i.

  for (int i = 1; i <= n; i++) mas[i][0] = i;

Для $j > 0$ j > 0 порівнюємо елементи масиву $a$ з індексами $ma s [i] [j - 1]$ mas[i][j - 1] та $ma s [i + 2^{j - 1}] [j - 1]$ mas[i + 2^{j-1}][j - 1] — максимуми на двох половинах відрізка — і зберігаємо індекс більшого з них.

  for (int j = 1; (1 << j) <= n; j++)
    for (int i = 1; i + (1 << j) - 1 <= n; i++)
      if (a[mas[i][j - 1]] > a[mas[i + (1 << (j - 1))][j - 1]])
        mas[i][j] = mas[i][j - 1];
      else mas[i][j] = mas[i + (1 << (j - 1))][j - 1];
}

Функція RangeMaxQuery повертає індекс максимального елемента на відрізку $[i; j]$ .

int RangeMaxQuery(int i, int j)
{
  int temp, k = 0;

Якщо $i > j$ i > j, межі міняються місцями.

  if (i > j) temp = i, i = j, j = temp;

Далі, в циклі, знаходимо найбільше $k$ таке, що $2^{k} \leq j - i + 1$ 2^k \le j - i + 1.

  while ((1 << (k + 1)) <= j - i + 1) k++;

Порівнюємо елементи з індексами $ma s [i] [k]$ mas[i][k] та $ma s [j - 2^{k} + 1] [k]$ mas[j - 2^k + 1][k] і повертаємо індекс більшого з них.

  return (a[mas[i][k]] >= a[mas[j - (1 << k) + 1][k]]) ?
         mas[i][k] : mas[j - (1 << k) + 1][k];
}

Основна частина програми. Зчитуємо розмір масиву $n$ та його елементи, починаючи з індексу $1$ .

scanf("%d", &n);
for (i = 1; i <= n; i++)
  scanf("%d", &a[i]);

Будуємо розріджену таблицю $ma s$ з масиву $a$ .

Build_RMQ_Array();

Зчитуємо кількість запитів $q$ .

scanf("%d", &q);

Для кожного запиту функція RangeMaxQuery повертає індекс $in d e x$ максимального елемента на відрізку $[u; v]$ , і ми виводимо сам елемент $a [in d e x]$ .

for (i = 0; i < q; i++)
{
  scanf("%d %d", &u, &v);
  int index = RangeMaxQuery(u, v);
  printf("%d\n", a[index]);
}

Реалізація алгоритму — максимум

Вхідна послідовність $a_{i}$ a_i ( $n \leq 1 0^{5}$ n \le 10^5) зберігається в масиві $a$ , починаючи з індексу $1$ . У цьому варіанті клітинка $ma s [i] [j]$ mas[i][j] зберігає сам максимум на відрізку $[i; i + 2^{j} - 1]$ [i; i + 2^j - 1]. Оскільки $2^{16} \leq 1 0^{5} < 2^{17}$ 2^{16} \le 10^5 < 2^{17}, для другого виміру достатньо $L O GM A X = 17$ LOGMAX = 17.

#define MAX 100010
#define LOGMAX 17
int mas[MAX][LOGMAX];
int a[MAX];

Функція Build_RMQ_Array будує розріджену таблицю з масиву $b$ :

ma s [i] [j] = max (b [i], b [i + 1], \dots, b [i + 2^{j} - 1])

mas[i][j] = \max(b[i], b[i + 1], \ldots, b[i + 2^j - 1])

void Build_RMQ_Array(int *b)
{

Для $j = 0$ j = 0 розріджена таблиця містить вихідні елементи масиву: $ma s [i] [0] = b [i]$ mas[i][0] = b[i].

  for (int i = 1; i <= n; i++) mas[i][0] = b[i];

Для $j > 0$ j > 0 значення $ma s [i] [j]$ mas[i][j] дорівнює більшому з максимумів на двох половинах відрізка.

  for (int j = 1; 1 << j <= n; j++)
    for (int i = 1; i + (1 << j) - 1 <= n; i++)
      mas[i][j] = max(mas[i][j - 1], mas[i + (1 << (j - 1))][j - 1]);
}

Функція RangeMaxQuery повертає максимум на відрізку $[i; j]$ .

int RangeMaxQuery(int i, int j)
{
  int temp, k = 0;

Якщо $i > j$ i > j, межі міняються місцями.

  if (i > j) temp = i, i = j, j = temp;

В циклі знаходимо найбільше $k$ таке, що $2^{k} \leq j - i + 1$ 2^k \le j - i + 1. Такий спосіб обчислення $k$ не вимагає функції логарифма і не залежить від похибок обчислень з рухомою комою.

  while ((1 << (k + 1)) <= j - i + 1) k++;

Відповідь — більший з максимумів на відрізках $[i; i + 2^{k} - 1]$ [i; i + 2^k - 1] та $[j - 2^{k} + 1; j]$ [j - 2^k + 1; j].

  return max(mas[i][k],mas[j - (1<<k) + 1][k]);
}

Основна частина програми. Зчитуємо розмір масиву $n$ та його елементи, починаючи з індексу $1$ .

scanf("%d",&n);
for(i = 1; i <= n; i++) scanf("%d",&a[i]);

Будуємо розріджену таблицю $ma s$ з масиву $a$ .

Build_RMQ_Array(a);

Зчитуємо кількість запитів $q$ . Для кожного запиту виводимо максимум на відрізку $[u; v]$ .

scanf("%d",&q);
for(i = 0; i < q; i++)
{
  scanf("%d %d",&u,&v);
  printf("%d\n",RangeMaxQuery(u,v));
}