Розріджені таблиці (Розбір)

Задача вимагає багаторазово знаходити мінімум на відрізку масиву, який не змінюється після генерації. Кількість запитів сягає $1 0^{7}$ 10^7, тому кожен запит потрібно обробляти за $O (1)$ . Для цього використовується sparse table — статична структура даних для задачі RMQ (Range Minimum Query).

Побудова таблиці. Для кожної позиції $i$ та кожного $j$ такого, що $i + 2^{j} - 1 \leq n$ i + 2^j - 1 \le n, у клітинці $ma s [i] [j]$ mas[i][j] зберігається індекс мінімального елемента на відрізку $[i; i + 2^{j} - 1]$ [i; i + 2^j - 1] довжини $2^{j}$ 2^j. Для $j = 0$ j = 0 відрізок складається з одного елемента, тому $ma s [i] [0] = i$ mas[i][0] = i.

Для $j > 0$ j > 0 розіб'ємо відрізок довжини $2^{j}$ 2^j на дві половини довжини $2^{j - 1}$ 2^{j-1}: $[i; i + 2^{j - 1} - 1]$ [i; i + 2^{j-1} - 1] та $[i + 2^{j - 1}; i + 2^{j} - 1]$ [i + 2^{j-1}; i + 2^j - 1]. Індекси мінімумів на половинах уже обчислено — це $ma s [i] [j - 1]$ mas[i][j - 1] та $ma s [i + 2^{j - 1}] [j - 1]$ mas[i + 2^{j-1}][j - 1]:

Мінімум усього відрізка дорівнює меншому з двох мінімумів половин. Тому $ma s [i] [j]$ mas[i][j] дорівнює тому з індексів $ma s [i] [j - 1]$ mas[i][j - 1] та $ma s [i + 2^{j - 1}] [j - 1]$ mas[i + 2^{j-1}][j - 1], який вказує на менший елемент масиву. Таблиця заповнюється у порядку зростання $j$ і містить $O (n lo g n)$ O(n \log n) клітинок.

Відповідь на запит. Нехай потрібно знайти мінімум на відрізку $[u; v]$ . Нехай $k = ⌊ lo g_{2} (v - u + 1)⌋$ k = \lfloor \log_2(v - u + 1) \rfloor — показник найбільшого степеня двійки, що не перевищує довжину відрізка. Відрізок довжини $2^{k}$ 2^k, що починається з $u$ , та відрізок довжини $2^{k}$ 2^k, що закінчується в $v$ , разом повністю покривають $[u; v]$ , оскільки $2 \cdot 2^{k} > v - u + 1$ 2 \cdot 2^k > v - u + 1:

Ці відрізки можуть перекриватися, але для мінімуму це не має значення: елемент, врахований двічі, не змінює результат (на відміну, наприклад, від суми). Тому мінімум на $[u; v]$ дорівнює меншому з елементів $a [ma s [u] [k]]$ a[mas[u][k]] та $a [ma s [v - 2^{k} + 1] [k]]$ a[mas[v - 2^k + 1][k]], а запит обробляється за $O (1)$ .

Межі $u$ та $v$ згенерованих запитів можуть надходити у будь-якому порядку, тому перед виконанням запиту ми міняємо їх місцями, якщо потрібно.

Складність. Побудова таблиці займає $O (n lo g n)$ O(n \log n), а кожен запит — $O (1)$ . Загальна складність становить $O (n lo g n + m)$ O(n \log n + m). При $m \leq 1 0^{7}$ m \le 10^7 саме обробка запиту за $O (1)$ дозволяє вкластися в обмеження за часом.

Приклад

Розглянемо приклад: $n = 10$ n = 10, $m = 8$ m = 8, $a_{1} = 12345$ a_1 = 12345. Згенерований масив збігається з масивом, наведеним в умові задачі. Таблиця $ma s$ для нього наведена нижче. Клітинки містять індекси мінімальних елементів; прочерк означає, що відрізок виходить за межі масиву.

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

Наприклад, $ma s [3] [2] = 5$ mas[3][2] = 5: на відрізку $[3; 6]$ мінімальним є елемент $a_{5} = 1565158$ a_5 = 1565158. Значення $ma s [2] [3] = 2$ mas[2][3] = 2 отримане з $ma s [2] [2] = 2$ mas[2][2] = 2 та $ma s [6] [2] = 8$ mas[6][2] = 8, оскільки $a_{2} = 305498 < a_{8} = 570265$ a_2 = 305498 < a_8 = 570265.

Перший запит: $u_{1} = 3$ u_1 = 3, $v_{1} = 9$ v_1 = 9. Довжина відрізка дорівнює $7$ , тому $k = 2$ k = 2. Відрізок $[3; 9]$ покривається відрізками $[3; 6]$ та $[6; 9]$ , для яких $ma s [3] [2] = 5$ mas[3][2] = 5 та $ma s [6] [2] = 8$ mas[6][2] = 8. Оскільки $a_{8} = 570265 < a_{5} = 1565158$ a_8 = 570265 < a_5 = 1565158, відповідь $an s_{1} = 570265$ ans_1 = 570265.

Параметри другого запиту:

u_{2} = ((17 \cdot 3 + 751 + 570265 + 2) mod 10) + 1 = 10, v_{2} = ((13 \cdot 9 + 593 + 570265 + 5) mod 10) + 1 = 1.

u_2 = ((17 \cdot 3 + 751 + 570265 + 2) \bmod 10) + 1 = 10, \\ v_2 = ((13 \cdot 9 + 593 + 570265 + 5) \bmod 10) + 1 = 1.

Оскільки $u_{2} > v_{2}$ u_2 > v_2, межі міняються місцями, і обчислюється мінімум на відрізку $[1; 10]$ .

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

$i$	$u_{i}$ \boldsymbol{u_i}	$v_{i}$ \boldsymbol{v_i}	відрізок	$an s_{i}$ \boldsymbol{ans_i}
$1$	$3$	$9$	$[3; 9]$	$570265$
$2$	$10$	$1$	$[1; 10]$	$12345$
$3$	$1$	$2$	$[1; 2]$	$12345$
$4$	$10$	$10$	$[10; 10]$	$1325095$
$5$	$5$	$9$	$[5; 9]$	$570265$
$6$	$2$	$1$	$[1; 2]$	$12345$
$7$	$3$	$2$	$[2; 3]$	$305498$
$8$	$5$	$3$	$[3; 5]$	$1565158$

Останній запит має параметри $u_{8} = 5$ u_8 = 5, $v_{8} = 3$ v_8 = 3, а його відповідь $an s_{8} = 1565158$ ans_8 = 1565158. Саме ці значення й виводяться. Зауважте, що виводяться вихідні значення $u_{8}$ u_8 та $v_{8}$ v_8, а не впорядковані межі відрізка.

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

Елементи масиву $a$ ( $n \leq 1 0^{5}$ n \le 10^5) зберігаються, починаючи з індексу $1$ . Sparse table зберігається у масиві $ma s$ : $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}, значення $j$ не перевищують $16$ , тому для другого виміру достатньо $L O GM A X = 17$ LOGMAX = 17.

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

Функція check міняє місцями значення $u$ та $v$ , якщо $u > v$ u > v, щоб виконувалось $u \leq v$ u \le v. Параметри передаються за посиланням.

void check(int &u, int &v)
{
  int temp;
  if (u > v) temp = u, u = v, v = temp;
}

Функція RMQ_nlogn будує sparse table.

void RMQ_nlogn(void)
{
  int i, j;

Спочатку $ma s [i] [0] = i$ mas[i][0] = i для всіх $i$ .

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

Потім для кожного $j$ , поки $2^{j} \leq n$ 2^j \le n, і для кожного $i$ такого, що відрізок $[i; i + 2^{j} - 1]$ [i; i + 2^j - 1] не виходить за межі масиву, обираємо з $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 (j = 1; (1 << j) <= n; j++)
    for (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];
}

Функція q повертає індекс мінімального елемента на відрізку $[i; j]$ . Обчислюємо $k = ⌊ lo g_{2} (j - i + 1)⌋$ k = \lfloor \log_2(j - i + 1) \rfloor і порівнюємо мінімуми двох відрізків довжини $2^{k}$ 2^k: $[i; i + 2^{k} - 1]$ [i; i + 2^k - 1] та $[j - 2^{k} + 1; j]$ [j - 2^k + 1; j].

int q(int i, int j)
{
  int k = (int)(log(1.0*j - i + 1) / log(2.0));
  int res = mas[i][k];
  if (a[mas[j - (1<<k) + 1][k]] < a[res])
      res = mas[j - (1<<k) + 1][k];
  return res;
}

C++

Основна частина програми. Зчитуємо $n$ , $m$ , перший елемент масиву $a_{1}$ a_1 та параметри першого запиту $u$ і $v$ .

scanf("%d %d",&n,&m);
scanf("%d %d %d",&a[1],&u,&v);

Генеруємо елементи $a_{2}, a_{3}, \dots, a_{n}$ a_2, a_3, \ldots, a_n за формулою з умови задачі. Добуток $23 \cdot a_{i}$ 23 \cdot a_i не перевищує $23 \cdot 16714589 \approx 3.8 \cdot 1 0^{8}$ 23 \cdot 16714589 \approx 3.8 \cdot 10^8 і вміщується в тип $in t$ .

for(i = 2; i <= n; i++)
  a[i] = (23 * a[i-1] + 21563) % 16714589;

Будуємо sparse table $ma s$ .

RMQ_nlogn();

Обробляємо $m$ запитів по черзі.

for (i = 1; i <= m; i++)
{

Копіюємо межі поточного запиту у $u 1$ та $v 1$ і, якщо потрібно, впорядковуємо їх за допомогою функції check. Самі значення $u$ та $v$ не змінюються: з них обчислюються параметри наступного запиту, і саме вони виводяться у відповіді.

  u1 = u; v1 = v; check(u1,v1);

Знаходимо мінімальний елемент на відрізку $[u 1; v 1]$ [u1; v1].

  ans = a[q(u1,v1)];

Якщо запит не останній, обчислюємо параметри наступного запиту за формулами з умови задачі.

  if (i < m)
  {
    u = ((17*u + 751 + ans + 2*i) % n) + 1;
    v = ((13*v + 593 + ans + 5*i) % n) + 1;
  }
}

Виводимо параметри останнього запиту та його відповідь.

printf("%d %d %d\n",u,v,ans);