**RMQ $O(n)/O(1)$**↵
↵
<spoiler summary="Задача">↵
Дан массив $a$ из $n$ чисел от $1$ до $10^9$.↵
Нужно уметь отвечать на запрос минимум на отрезке с $l$ по $r$ за $O(1)$ в онлайне и $O(n)$ предподсчета.↵
</spoiler>↵
↵
Для удобства будем считать, что нумерация массива с нуля.↵
↵
Разобьем наш массив на блоки по $\lceil\log_{2}(n)\rceil$ чисел. Для удобства обозначим $bl = \lceil\log_{2}(n)\rceil$. В первом блоке числа с $a_{0}$ до $a_{bl - 1}$, во втором с $a_{bl}$ до $a_{2 * bl - 1}$ и так далее, в последнем блоке может быть меньше $bl$ чисел.↵
↵
Таким образом, мы получили $\lceil\frac{n}{bl}\rceil$ блоков. Научимся находить минимум для отрезка, находящегося целиком внутри блока.↵
↵
Будем рассматривать блоки независимо, в каждом блоке пойдем слева направо и будем поддерживать стек минимумов. Для каждой граинцы $r$ запомним стек минимумов с начала блока, в котором находится $r$, заканчивая $r$. Будем запоминать стек минимумов, как маску нулей и единиц, в $iм$ бите будет стоять $1$, если $iе$ число в блоке сейчас в стеке минимумов. ↵
↵
Пусть мы теперь хотим найти минимум на отрезке с $l$ до $r$, и $l$ в одном блоке с $r$. Заметим, что минимум стоит на позиции самого левого единичного бита позже $lго$(или $lй$) из стека минимума, который мы запомнили в $r$.↵
Пусть в $r$ маска стека минимумов — $mask$. Тогда нужный нам единичный бит — первый бит в $mask >> (l - start_{l})$, где↵
$start_{l}$ — начало блока. $start_{l} = \lfloor\frac{l}{bl}\rfloor * bl$. Всего различных масок $2^{bl}$ < $2 * n$, так что с помощью динамического программирования мы можем для каждой маски предподсчитать индекс ее самого левого единичного бита. ↵
↵
Таким образом, мы сделали предподсчет $O(n)$ и умеем находить минимум на отрезке внутри блока. Теперь надо научиться искать минимум, если $l$ и $r$ в разных блоках. Тогда нужный нам минимум — это $min(getmin(l, end_{l}), getmin(start_{r}, r), getmin(end_{l} + 1, start_{r} - 1))$. Первые 2 величины мы умеем искать, так как границы в одном блоке, а третья величина — минимум на подотрезке блоков. Тогда, найдем минимум в каждого блоке и построим sparse table на массиве из этих минимумов. Предподсчет sparse table $O(\lceil\frac{n}{bl}\rceil * log_{2}(\lceil\frac{n}{bl}\rceil))$, то есть $O(n)$. ↵
↵
Мы научились за $O(n)$ предподсчета искать минимум на отрезке за $O(1)$.↵
↵
При $n = 10^6$ моя реализация этого алгоритма работает столько же, сколько дерево отрезков снизу, но, скорее всего, можно реализовать лучше.↵
↵
<spoiler summary="Код">↵
```↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
const int INF = 1e9;↵
↵
inline int get_min_sparse_table(int l, int r, vector <vector <int>>& st, vector <int>& max_st2) {↵
if (l > r) return INF;↵
int len = r - l + 1;↵
return min(st[max_st2[len]][l], st[max_st2[len]][r - (1 << max_st2[len]) + 1]);↵
}↵
↵
inline int get_min_in_block(vector <int>& a, int l, int r, vector <int>& first_bit, vector <int>& stack_min_mask, int left_block) {↵
return a[first_bit[(stack_min_mask[r] >> (l - left_block))] + l];↵
}↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(nullptr);↵
cout.tie(nullptr);↵
int n, m;↵
cin >> n >> m;↵
vector <int> a(n);↵
for (int i = 0; i < n; ++i) cin >> a[i];↵
int lg = (int)ceil(log2(n));↵
vector <int> first_bit(1 << lg);↵
for (int i = 0; i < lg; ++i) {↵
for (int mask = 1; mask < (1 << i); ++mask) {↵
first_bit[mask + (1 << i)] = first_bit[mask];↵
}↵
first_bit[(1 << i)] = i;↵
}↵
vector <int> all_blocks_min;↵
vector <int> stack_min_mask(n);↵
vector <int> stack_min;↵
for (int i = 0; i < n; i += lg) {↵
stack_min.clear();↵
int cur_min = a[i];↵
for (int j = i; j < min(i + lg, n); ++j) {↵
cur_min = min(cur_min, a[j]);↵
}↵
all_blocks_min.push_back(cur_min);↵
int cur_mask = 0;↵
for (int j = i; j < min(i + lg, n); ++j) {↵
while (!stack_min.empty() && a[stack_min.back()] >= a[j]) {↵
cur_mask -= (1 << (stack_min.back() - i));↵
stack_min.pop_back();↵
}↵
cur_mask += (1 << (j - i));↵
stack_min_mask[j] = cur_mask;↵
stack_min.push_back(j);↵
}↵
}↵
int new_len = (int)all_blocks_min.size();↵
int new_lg = (int)ceil(log2(new_len));↵
vector <vector <int>> st(new_lg, vector <int> (new_len));↵
for (int len = 0; len < new_lg; ++len) {↵
for (int start = 0; start + (1 << len) - 1 < new_len; ++start) {↵
if (len == 0) st[len][start] = all_blocks_min[start];↵
else st[len][start] = min(st[len - 1][start], st[len - 1][start + (1 << (len - 1))]);↵
}↵
}↵
vector <int> max_st2(new_len + 1);↵
for (int i = 2; i <= new_len; ++i) {↵
max_st2[i] = max_st2[i / 2] + 1;↵
}↵
while (m--) {↵
int l, r;↵
cin >> l >> r; --l; --r;↵
int block_l = l / lg, block_r = r / lg;↵
if (block_l == block_r) cout << get_min_in_block(a, l, r, first_bit, stack_min_mask, block_l * lg) << "\n";↵
else {↵
cout << min(min(get_min_in_block(a, l, lg * (block_l + 1) - 1, first_bit, stack_min_mask, block_l * lg),↵
get_min_in_block(a, block_r * lg, r, first_bit, stack_min_mask, block_r * lg)),↵
get_min_sparse_table(block_l + 1, block_r - 1, st, max_st2)) << "\n";↵
}↵
}↵
}↵
```↵
</spoiler>↵
↵
**Улучшенная версия этого алгоритма, поддерживающая изменения**↵
↵
<spoiler summary="Задача">↵
Дан массив $a$ из $n$ чисел от $1$ до $10^9$.↵
Нужно уметь отвечать на запрос минимум на отрезке с $l$ по $r$ и уметь делать $a_{i} = x$.↵
</spoiler>↵
↵
Недавно я задумался, как можно изменять эту структуру и придумал, что вместо sparse table на минимумах в блоках, можно еще раз разбить на блоки по $log_{2}(n)$, посчитать стеки минимумов и снова сделать ту же структру. Фактически, будем несколько уровней структуры, на каждом надо поддерживать нужные маски и размеры блоков. Будем сокращать длину следующего уровня до тех пор, пока количество чисел на уровне больше $2$.↵
На каждом уровне количество чисел сокращается в $log_{2}(len)$, где $len$ — длина массива на последнем уровне. На каждом уровне предподсчет линеен.↵
↵
Таким образом, пусть $f(n) = f(\lceil\frac{n}{\lceil\log_{2}(n)\rceil}\rceil) + n$, тогда на предподсчет нужно $O(f(n))$.↵
↵
Рассмотрим запрос обновления:↵
У нас изменится стек минимумов в одном блоке на самом длиннов уровне, так что пересчитаем его в тупую, затем может измениться минимум в блоке, так что надо пересчитать стек минимумов в одном блоке на уровне выше и так далее.↵
Таким образом, пусть $g(n) = g(\lceil\frac{n}{\lceil\log_{2}(n)\rceil}\rceil) + \log_{2}(n)$, тогда на запрос обновления $O(g(n))$.↵
↵
Рассмотрим запрос минимума на отрезке:↵
Если границы в одном блоке на самом длинном уровне, то просто найдем ответ. Иначе, нам надо найти минимум в маленьком подотрезке слева(за $O(1)$, в маленьком подтрезке справа(за $O(1)$) и на подотрезке из блоков. ↵
Таким образом, пусть $t(n) = t(\lceil\frac{n}{\lceil\log_{2}(n)\rceil}\rceil) + 1$, тогда на запрос минимума на отрезке $O(t(n))$.↵
↵
Получается, операция update дольше $O(log_{2}(n))$, но быстрее $O(log_{2}(n)^2)$(так как уровней не больше $log_{2}(n)$ и на каждом длина блока не больше $log_{2}(n)$. Более точную оценку я дать не могу.↵
↵
Операция get быстрее $O(log_{2}(n))$, так как каждый раз длина уровня сокращается не меньше, чем в $2$ раза. Опять же, я не знаю как это оценить точнее, но я провел тесты.↵
↵
При $n = 10^6$, эта структра работает в среднем $1250мс$, рекурсивное дерево отрезков $850мс$, дерево отрезков снизу↵
$680мс$. ↵
↵
Когда запросов get в $100$ раз больше, чем запросов update, эта структра работает в среднем $1170мс$, рекурсивное дерево отрезков $1600мс$, дерево отрезков снизу $1200мс$. Не знаю, почему время работы моей структуры не сильно изменилось, скорее всего из-за константы, но по идее должно работать сильно быстрее, так как при $n = 10^6$, ↵
$t(n) = 6$, $g(n) = 65$. $f(n) = 1053421$, что почти $10^6$.↵
Тесты, которые я делал рандомные.↵
↵
<spoiler summary="Код">↵
```↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
int INF = 1e9;↵
↵
signed main() {↵
if (1) {↵
ios_base::sync_with_stdio(false);↵
cin.tie(nullptr);↵
cout.tie(nullptr);↵
}↵
int n, m;↵
cin >> n >> m;↵
vector <int> a(n);↵
for (int i = 0; i < n; ++i) cin >> a[i];↵
vector <int> block_sizes;↵
vector <vector <int>> all_levels_values;↵
vector <vector <int>> all_stack_min_masks;↵
int max_lg = (int)ceil(log2(n));↵
vector <int> pre_calc((1 << max_lg));↵
for (int i = 0; i < max_lg; ++i) {↵
for (int mask = 1; mask < (1 << i); ++mask) {↵
pre_calc[mask + (1 << i)] = pre_calc[mask];↵
}↵
pre_calc[1 << i] = i;↵
}↵
all_levels_values.push_back(a);↵
block_sizes.push_back(max_lg);↵
while (true) {↵
all_stack_min_masks.push_back({});↵
for (int i = 0; i < all_levels_values.back().size(); i += block_sizes.back()) {↵
int cur_mask = 0;↵
vector <int> stack_min;↵
for (int j = i; j < min((int)all_levels_values.back().size(), i + block_sizes.back()); ++j) {↵
while (!stack_min.empty() && all_levels_values.back()[stack_min.back()] >= all_levels_values.back()[j]) {↵
cur_mask -= (1 << (stack_min.back() - i));↵
stack_min.pop_back();↵
}↵
stack_min.push_back(j);↵
cur_mask += (1 << (j - i));↵
all_stack_min_masks.back().push_back(cur_mask);↵
}↵
}↵
if (all_levels_values.back().size() > 1) {↵
vector <int> now = all_levels_values.back();↵
all_levels_values.push_back({});↵
for (int i = 0; i < now.size(); i += block_sizes.back()) {↵
int minn = now[i];↵
for (int j = i; j < min((int)now.size(), i + block_sizes.back()); ++j) minn = min(minn, now[j]);↵
all_levels_values.back().push_back(minn);↵
}↵
block_sizes.push_back(max((int)ceil(log2((int)all_levels_values.back().size())), 2));↵
} else break;↵
}↵
while (m--) {↵
int type;↵
cin >> type;↵
if (type == 1) {↵
int i, x;↵
cin >> i >> x; --i;↵
for (int lvl = 0; lvl < (int)all_levels_values.size(); ++lvl) {↵
all_levels_values[lvl][i] = x;↵
int start = i / block_sizes[lvl] * block_sizes[lvl];↵
vector <int> stack_min;↵
int cur_mask = 0, minn = INF;↵
for (int j = start; j < min((int)all_levels_values[lvl].size(), start + block_sizes[lvl]); ++j) {↵
while (!stack_min.empty() && all_levels_values[lvl][stack_min.back()] >= all_levels_values[lvl][j]) {↵
cur_mask -= (1 << (stack_min.back() - start));↵
stack_min.pop_back();↵
}↵
minn = min(minn, all_levels_values[lvl][j]);↵
stack_min.push_back(j);↵
cur_mask += (1 << (j - start));↵
all_stack_min_masks[lvl][j] = cur_mask;↵
}↵
x = minn;↵
i /= block_sizes[lvl];↵
}↵
} else {↵
int l, r;↵
cin >> l >> r; --l; --r;↵
if (l == 0 && r == n - 1) {↵
cout << all_levels_values.back().back() << "\n";↵
continue;↵
}↵
int minn = INF;↵
for (int lvl = 0; lvl < (int)all_levels_values.size(); ++lvl) {↵
if (l > r) break;↵
int start_l = l / block_sizes[lvl] * block_sizes[lvl];↵
int start_r = r / block_sizes[lvl] * block_sizes[lvl];↵
if (start_l == start_r) {↵
int new_mask = (all_stack_min_masks[lvl][r] >> (l - start_l));↵
int ans = all_levels_values[lvl][start_l + pre_calc[new_mask] + l - start_l];↵
minn = min(minn, ans);↵
break;↵
}↵
int new_mask = (all_stack_min_masks[lvl][start_l + block_sizes[lvl] - 1] >> (l - start_l));↵
minn = min(minn, all_levels_values[lvl][start_l + pre_calc[new_mask] + l - start_l]);↵
new_mask = all_stack_min_masks[lvl][r];↵
minn = min(minn, all_levels_values[lvl][start_r + pre_calc[new_mask]]);↵
l /= block_sizes[lvl];↵
r /= block_sizes[lvl];↵
++l;↵
--r;↵
}↵
cout << minn << "\n";↵
}↵
}↵
}↵
```↵
</spoiler>↵
↵
↵
<spoiler summary="Задача">↵
Дан массив $a$ из $n$ чисел от $1$ до $10^9$.↵
Нужно уметь отвечать на запрос минимум на отрезке с $l$ по $r$ за $O(1)$ в онлайне и $O(n)$ предподсчета.↵
</spoiler>↵
↵
Для удобства будем считать, что нумерация массива с нуля.↵
↵
Разобьем наш массив на блоки по $\lceil\log_{2}(n)\rceil$ чисел. Для удобства обозначим $bl = \lceil\log_{2}(n)\rceil$. В первом блоке числа с $a_{0}$ до $a_{bl - 1}$, во втором с $a_{bl}$ до $a_{2 * bl - 1}$ и так далее, в последнем блоке может быть меньше $bl$ чисел.↵
↵
Таким образом, мы получили $\lceil\frac{n}{bl}\rceil$ блоков. Научимся находить минимум для отрезка, находящегося целиком внутри блока.↵
↵
Будем рассматривать блоки независимо, в каждом блоке пойдем слева направо и будем поддерживать стек минимумов. Для каждой граинцы $r$ запомним стек минимумов с начала блока, в котором находится $r$, заканчивая $r$. Будем запоминать стек минимумов, как маску нулей и единиц, в $iм$ бите будет стоять $1$, если $iе$ число в блоке сейчас в стеке минимумов. ↵
↵
Пусть мы теперь хотим найти минимум на отрезке с $l$ до $r$, и $l$ в одном блоке с $r$. Заметим, что минимум стоит на позиции самого левого единичного бита позже $lго$(или $lй$) из стека минимума, который мы запомнили в $r$.↵
Пусть в $r$ маска стека минимумов — $mask$. Тогда нужный нам единичный бит — первый бит в $mask >> (l - start_{l})$, где↵
$start_{l}$ — начало блока. $start_{l} = \lfloor\frac{l}{bl}\rfloor * bl$. Всего различных масок $2^{bl}$ < $2 * n$, так что с помощью динамического программирования мы можем для каждой маски предподсчитать индекс ее самого левого единичного бита. ↵
↵
Таким образом, мы сделали предподсчет $O(n)$ и умеем находить минимум на отрезке внутри блока. Теперь надо научиться искать минимум, если $l$ и $r$ в разных блоках. Тогда нужный нам минимум — это $min(getmin(l, end_{l}), getmin(start_{r}, r), getmin(end_{l} + 1, start_{r} - 1))$. Первые 2 величины мы умеем искать, так как границы в одном блоке, а третья величина — минимум на подотрезке блоков. Тогда, найдем минимум в каждого блоке и построим sparse table на массиве из этих минимумов. Предподсчет sparse table $O(\lceil\frac{n}{bl}\rceil * log_{2}(\lceil\frac{n}{bl}\rceil))$, то есть $O(n)$. ↵
↵
Мы научились за $O(n)$ предподсчета искать минимум на отрезке за $O(1)$.↵
↵
При $n = 10^6$ моя реализация этого алгоритма работает столько же, сколько дерево отрезков снизу, но, скорее всего, можно реализовать лучше.↵
↵
<spoiler summary="Код">↵
```↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
const int INF = 1e9;↵
↵
inline int get_min_sparse_table(int l, int r, vector <vector <int>>& st, vector <int>& max_st2) {↵
if (l > r) return INF;↵
int len = r - l + 1;↵
return min(st[max_st2[len]][l], st[max_st2[len]][r - (1 << max_st2[len]) + 1]);↵
}↵
↵
inline int get_min_in_block(vector <int>& a, int l, int r, vector <int>& first_bit, vector <int>& stack_min_mask, int left_block) {↵
return a[first_bit[(stack_min_mask[r] >> (l - left_block))] + l];↵
}↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(nullptr);↵
cout.tie(nullptr);↵
int n, m;↵
cin >> n >> m;↵
vector <int> a(n);↵
for (int i = 0; i < n; ++i) cin >> a[i];↵
int lg = (int)ceil(log2(n));↵
vector <int> first_bit(1 << lg);↵
for (int i = 0; i < lg; ++i) {↵
for (int mask = 1; mask < (1 << i); ++mask) {↵
first_bit[mask + (1 << i)] = first_bit[mask];↵
}↵
first_bit[(1 << i)] = i;↵
}↵
vector <int> all_blocks_min;↵
vector <int> stack_min_mask(n);↵
vector <int> stack_min;↵
for (int i = 0; i < n; i += lg) {↵
stack_min.clear();↵
int cur_min = a[i];↵
for (int j = i; j < min(i + lg, n); ++j) {↵
cur_min = min(cur_min, a[j]);↵
}↵
all_blocks_min.push_back(cur_min);↵
int cur_mask = 0;↵
for (int j = i; j < min(i + lg, n); ++j) {↵
while (!stack_min.empty() && a[stack_min.back()] >= a[j]) {↵
cur_mask -= (1 << (stack_min.back() - i));↵
stack_min.pop_back();↵
}↵
cur_mask += (1 << (j - i));↵
stack_min_mask[j] = cur_mask;↵
stack_min.push_back(j);↵
}↵
}↵
int new_len = (int)all_blocks_min.size();↵
int new_lg = (int)ceil(log2(new_len));↵
vector <vector <int>> st(new_lg, vector <int> (new_len));↵
for (int len = 0; len < new_lg; ++len) {↵
for (int start = 0; start + (1 << len) - 1 < new_len; ++start) {↵
if (len == 0) st[len][start] = all_blocks_min[start];↵
else st[len][start] = min(st[len - 1][start], st[len - 1][start + (1 << (len - 1))]);↵
}↵
}↵
vector <int> max_st2(new_len + 1);↵
for (int i = 2; i <= new_len; ++i) {↵
max_st2[i] = max_st2[i / 2] + 1;↵
}↵
while (m--) {↵
int l, r;↵
cin >> l >> r; --l; --r;↵
int block_l = l / lg, block_r = r / lg;↵
if (block_l == block_r) cout << get_min_in_block(a, l, r, first_bit, stack_min_mask, block_l * lg) << "\n";↵
else {↵
cout << min(min(get_min_in_block(a, l, lg * (block_l + 1) - 1, first_bit, stack_min_mask, block_l * lg),↵
get_min_in_block(a, block_r * lg, r, first_bit, stack_min_mask, block_r * lg)),↵
get_min_sparse_table(block_l + 1, block_r - 1, st, max_st2)) << "\n";↵
}↵
}↵
}↵
```↵
</spoiler>↵
↵
**Улучшенная версия этого алгоритма, поддерживающая изменения**↵
↵
<spoiler summary="Задача">↵
Дан массив $a$ из $n$ чисел от $1$ до $10^9$.↵
Нужно уметь отвечать на запрос минимум на отрезке с $l$ по $r$ и уметь делать $a_{i} = x$.↵
</spoiler>↵
↵
Недавно я задумался, как можно изменять эту структуру и придумал, что вместо sparse table на минимумах в блоках, можно еще раз разбить на блоки по $log_{2}(n)$, посчитать стеки минимумов и снова сделать ту же структру. Фактически, будем несколько уровней структуры, на каждом надо поддерживать нужные маски и размеры блоков. Будем сокращать длину следующего уровня до тех пор, пока количество чисел на уровне больше $2$.↵
На каждом уровне количество чисел сокращается в $log_{2}(len)$, где $len$ — длина массива на последнем уровне. На каждом уровне предподсчет линеен.↵
↵
Таким образом, пусть $f(n) = f(\lceil\frac{n}{\lceil\log_{2}(n)\rceil}\rceil) + n$, тогда на предподсчет нужно $O(f(n))$.↵
↵
Рассмотрим запрос обновления:↵
У нас изменится стек минимумов в одном блоке на самом длиннов уровне, так что пересчитаем его в тупую, затем может измениться минимум в блоке, так что надо пересчитать стек минимумов в одном блоке на уровне выше и так далее.↵
Таким образом, пусть $g(n) = g(\lceil\frac{n}{\lceil\log_{2}(n)\rceil}\rceil) + \log_{2}(n)$, тогда на запрос обновления $O(g(n))$.↵
↵
Рассмотрим запрос минимума на отрезке:↵
Если границы в одном блоке на самом длинном уровне, то просто найдем ответ. Иначе, нам надо найти минимум в маленьком подотрезке слева(за $O(1)$, в маленьком подтрезке справа(за $O(1)$) и на подотрезке из блоков. ↵
Таким образом, пусть $t(n) = t(\lceil\frac{n}{\lceil\log_{2}(n)\rceil}\rceil) + 1$, тогда на запрос минимума на отрезке $O(t(n))$.↵
↵
Получается, операция update дольше $O(log_{2}(n))$, но быстрее $O(log_{2}(n)^2)$(так как уровней не больше $log_{2}(n)$ и на каждом длина блока не больше $log_{2}(n)$. Более точную оценку я дать не могу.↵
↵
Операция get быстрее $O(log_{2}(n))$, так как каждый раз длина уровня сокращается не меньше, чем в $2$ раза. Опять же, я не знаю как это оценить точнее, но я провел тесты.↵
↵
При $n = 10^6$, эта структра работает в среднем $1250мс$, рекурсивное дерево отрезков $850мс$, дерево отрезков снизу↵
$680мс$. ↵
↵
Когда запросов get в $100$ раз больше, чем запросов update, эта структра работает в среднем $1170мс$, рекурсивное дерево отрезков $1600мс$, дерево отрезков снизу $1200мс$. Не знаю, почему время работы моей структуры не сильно изменилось, скорее всего из-за константы, но по идее должно работать сильно быстрее, так как при $n = 10^6$, ↵
$t(n) = 6$, $g(n) = 65$. $f(n) = 1053421$, что почти $10^6$.↵
Тесты, которые я делал рандомные.↵
↵
<spoiler summary="Код">↵
```↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
int INF = 1e9;↵
↵
signed main() {↵
if (1) {↵
ios_base::sync_with_stdio(false);↵
cin.tie(nullptr);↵
cout.tie(nullptr);↵
}↵
int n, m;↵
cin >> n >> m;↵
vector <int> a(n);↵
for (int i = 0; i < n; ++i) cin >> a[i];↵
vector <int> block_sizes;↵
vector <vector <int>> all_levels_values;↵
vector <vector <int>> all_stack_min_masks;↵
int max_lg = (int)ceil(log2(n));↵
vector <int> pre_calc((1 << max_lg));↵
for (int i = 0; i < max_lg; ++i) {↵
for (int mask = 1; mask < (1 << i); ++mask) {↵
pre_calc[mask + (1 << i)] = pre_calc[mask];↵
}↵
pre_calc[1 << i] = i;↵
}↵
all_levels_values.push_back(a);↵
block_sizes.push_back(max_lg);↵
while (true) {↵
all_stack_min_masks.push_back({});↵
for (int i = 0; i < all_levels_values.back().size(); i += block_sizes.back()) {↵
int cur_mask = 0;↵
vector <int> stack_min;↵
for (int j = i; j < min((int)all_levels_values.back().size(), i + block_sizes.back()); ++j) {↵
while (!stack_min.empty() && all_levels_values.back()[stack_min.back()] >= all_levels_values.back()[j]) {↵
cur_mask -= (1 << (stack_min.back() - i));↵
stack_min.pop_back();↵
}↵
stack_min.push_back(j);↵
cur_mask += (1 << (j - i));↵
all_stack_min_masks.back().push_back(cur_mask);↵
}↵
}↵
if (all_levels_values.back().size() > 1) {↵
vector <int> now = all_levels_values.back();↵
all_levels_values.push_back({});↵
for (int i = 0; i < now.size(); i += block_sizes.back()) {↵
int minn = now[i];↵
for (int j = i; j < min((int)now.size(), i + block_sizes.back()); ++j) minn = min(minn, now[j]);↵
all_levels_values.back().push_back(minn);↵
}↵
block_sizes.push_back(max((int)ceil(log2((int)all_levels_values.back().size())), 2));↵
} else break;↵
}↵
while (m--) {↵
int type;↵
cin >> type;↵
if (type == 1) {↵
int i, x;↵
cin >> i >> x; --i;↵
for (int lvl = 0; lvl < (int)all_levels_values.size(); ++lvl) {↵
all_levels_values[lvl][i] = x;↵
int start = i / block_sizes[lvl] * block_sizes[lvl];↵
vector <int> stack_min;↵
int cur_mask = 0, minn = INF;↵
for (int j = start; j < min((int)all_levels_values[lvl].size(), start + block_sizes[lvl]); ++j) {↵
while (!stack_min.empty() && all_levels_values[lvl][stack_min.back()] >= all_levels_values[lvl][j]) {↵
cur_mask -= (1 << (stack_min.back() - start));↵
stack_min.pop_back();↵
}↵
minn = min(minn, all_levels_values[lvl][j]);↵
stack_min.push_back(j);↵
cur_mask += (1 << (j - start));↵
all_stack_min_masks[lvl][j] = cur_mask;↵
}↵
x = minn;↵
i /= block_sizes[lvl];↵
}↵
} else {↵
int l, r;↵
cin >> l >> r; --l; --r;↵
if (l == 0 && r == n - 1) {↵
cout << all_levels_values.back().back() << "\n";↵
continue;↵
}↵
int minn = INF;↵
for (int lvl = 0; lvl < (int)all_levels_values.size(); ++lvl) {↵
if (l > r) break;↵
int start_l = l / block_sizes[lvl] * block_sizes[lvl];↵
int start_r = r / block_sizes[lvl] * block_sizes[lvl];↵
if (start_l == start_r) {↵
int new_mask = (all_stack_min_masks[lvl][r] >> (l - start_l));↵
int ans = all_levels_values[lvl][start_l + pre_calc[new_mask] + l - start_l];↵
minn = min(minn, ans);↵
break;↵
}↵
int new_mask = (all_stack_min_masks[lvl][start_l + block_sizes[lvl] - 1] >> (l - start_l));↵
minn = min(minn, all_levels_values[lvl][start_l + pre_calc[new_mask] + l - start_l]);↵
new_mask = all_stack_min_masks[lvl][r];↵
minn = min(minn, all_levels_values[lvl][start_r + pre_calc[new_mask]]);↵
l /= block_sizes[lvl];↵
r /= block_sizes[lvl];↵
++l;↵
--r;↵
}↵
cout << minn << "\n";↵
}↵
}↵
}↵
```↵
</spoiler>↵
↵
