1632
правки
Изменения
м
<code>
</code>
rollbackEdits.php mass rollback
=== Псевдокод ===
'''function''' precalc(A: '''int[N]'''):
j = 0
i = 0
'''while''' i < N or j < Kblock_size '''if''' j <tex>\geqslant</tex> ≥ block_size
j = 0
cur_block++
'''for''' r = l + 1 '''to''' block_size - 1
block_min[t][l][r] = block_min[t][l][r - 1]
'''if''' i * block_size + r <tex>\leqslant </tex> ≤ N '''and''' A[i * block_size + block_min[t][l][r]] > A[i * block_size + r]
block_min[t][l][r] = r
'''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(blbr, 0, r % block_size)] <font color=green>// найдем минимум от начала блока, содержащего r, до r </font>
'''return''' min(ansb, min(ansl, ansr))
=== Результат ===
