69
правок
Изменения
Нет описания правки
{{Задача
|definition = Дан массив <tex>A[1 \ldots N]</tex> целых чисел, соседние элементы которой которого отличаются на <tex>\pm 1</tex>. Поступают онлайн запросы вида <tex>(l, r)</tex>, для каждого из которых требуется найти минимум среди элементов <tex>A[l], A[l + 1], \ldots, A[r] </tex>.
}}
Чтобы избавиться от логарифма используется предподсчёт ответа для небольших подстрок входной последовательности. Разделим последовательность <tex>A_i</tex> на блоки длины <tex>\frac{1}{2}\log_2 N</tex>. Для каждого блока вычислим минимум на нём и определим <tex>B_i</tex> как позицию минимального элемента в <tex>i</tex>-ом блоке.
На новой последовательности <tex>B_i</tex> построим [[Решение RMQ с помощью разреженной таблицы|разреженную таблицу]]. Теперь для ответа на запрос <tex>RMQ</tex><tex>[il:jr]</tex>, если <tex>il</tex> и <tex>jr</tex> находятся в разных блоках, нам необходимо вычислить следующее:# минимум на отрезке от <tex>il</tex> до конца блока, содержащего <tex>il</tex>;# минимум по всем блокам, находящимся между блоками, содержащими <tex>il</tex> и <tex>jr</tex>;# минимум от начала блока, содержащего <tex>jr</tex>, до <tex>jr</tex>.
Ответом на запрос будет позиция меньшего из эти трёх элементов.
[[Файл:F-C_B_algo.png|500px|center|Части, из которых состоит ответ на запрос RMQ]]
Второй элемент мы уже умеем находить за <tex>O(1)</tex> с помощью <tex>И_iB_i</tex> и ST. Осталось научиться находить минимум по отрезку, границы которого не совпадают с границами блоков.
=== Минимум внутри блока ===
=== Псевдокод ===
<code>
precalc(A : '''int[]''', N : '''int''')
block_size = log(N) / 2 <font color=green> // размеры блоков </font>
K = <tex>\lceil</tex>N / block_size<tex>\rceil</tex> <font color=green> // количество блоков </font>
<font color=green>// предподсчитаем позиции минимумов в каждом блоке</font>
cur_block = 0
j = 0
'''for''' i = 0 '''to''' K - 1
B[i] = -1
'''for''' i = 0 '''to''' N - 1
'''if''' j <tex>\ge</tex> block_size
j = 0
cur_block++
'''if''' B[cur_block] = -1 '''or''' A[B[cur_block]] > A[i]
B[cur_block] = i
<font color=green>// построим Sparse table на массиве B</font>
'''for''' i = 0 '''to''' K - 1
ST[i][0] = B[i]
'''for''' j = 1 '''to''' log(N)
'''for''' i = 0 '''to''' K - 1
ind = (1 << (j - 1)) + i
'''if''' ind <tex>\ge</tex> K
ST[i][j] = ST[i][j - 1]
'''else if''' A[ST[i][j - 1]] > A[ST[ind][j - 1]]
ST[i][j] = ST[ind][j - 1]
'''else'''
ST[i][j] = ST[i][j - 1]
<font color=green>// Посчитаем хеш для каждого блока {{---}} он будет являться типом блока</font>
cur_block = 0
j = 0
'''for''' i = 0 '''to''' K - 1
hash[i] = 0
'''for''' i = 0 '''to''' N - 1
'''if''' j <tex>\ge<tex> block_size
j = 0
cur_block++
'''if''' j > 0 '''and''' (i <tex>\ge</tex> n '''or''' A[i - 1] < A[i])
hash[cur_block] += (1 << (j - 1))
<font color=green>// Осталось только для каждого блока предподсчитать позиции минимумов на всех подотрезках</font>
'''for''' i = 0 '''to''' K - 1
'''for''' l = 0 '''to''' block_size - 1
'''for''' r = 0 '''to''' block_size - 1
block_min[i][l][r] = -1
'''for''' i = 0 '''to''' K - 1
type = hash[i]
'''if''' block_min[type][0][0] = -1 <font color=green>// если там записано, что-то отличное от -1, то значит, мы уже посчитали ответ для такого типа отрезков</font>
'''for''' l = 0 '''to''' block_size - 1
block_min[type][l][l] = l
'''for''' r = l + 1 '''to''' block_size - 1
block_min[type][l][r] = block_min[type][l][r - 1]
'''if''' i * block_size + r <tex>\le</tex> N '''and''' A[i * block_size + block_min[type][l][r]] > A[i * block_size + r]
block_min[type][l][r] = r
'''int''' block_RMQ(block_number : '''int''', l : '''int''', r : '''int''')
'''return''' block_min[hash[block_number]][l][r] + block_number * block_size
'''int''' RMQ(l : '''int''', r : '''int''')
bl = l / block_size
br = r / block_size
'''if''' bl = br <font color=green>// если оба индекса внутри одного блока</font>
'''return''' A[block_RMQ(bl, l % block_size, r % block_size)]
'''if''' bl + 1 < br <font color=green>// найдем минимум на блоках между крайними, если таковые есть</font>
power = log(br - bl + 1)
ansb = min(A[ST[bl + 1][power]], A[ST[br - (1 << power)][power]])
ansl = A[block_RMQ(bl, l % block_size, block_size - 1)] <font color=green>// найдем минимум на отрезке от l до конца блока, содержащего l</font>
ansr = A[block_RMQ(bl, 0, r % block_size)] <font color=green>// найдем минимум от начала блока, содержащего r, до r </font>
'''return''' min(ansb, min(ansl, ansr))
</code>
=== Результат ===
