Sparse table: различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) Нет описания правки |
Ctrlalt (обсуждение | вклад) (→Ссылки) |
||
Строка 15: | Строка 15: | ||
} | } | ||
}; | }; | ||
== Ссылки на задачи == | |||
* [http://codeforces.ru/gym/100093/problem/E Codeforces #100093.E — Разреженные таблицы] | |||
* [http://codeforces.ru/gym/100255/problem/A Codeforces #100255.A — Грибы] | |||
== Ссылки == | == Ссылки == |
Версия от 13:27, 26 октября 2014
class SparseTable { int lg[100010], st[20][100010]; public: SparseTable(int a[], int size) { for (int i = 0; i <= size; i++) lg[i] = (i > 1 ? lg[i / 2] + 1 : 0); for (int p = 0; (1 << p) <= size; p++) { for (int i = 0; i + (1 << p) <= size; i++) st[p][i] = (p ? min(st[p - 1][i], st[p - 1][i + (1 << p - 1)]) : a[i]); } } int getMin(int l, int r) { int p = lg[r - l + 1]; return min(t[p][l], t[p][r - (1 << p) + 1]); } };