Задача
Теперь у Вити есть программа, которая помогает ему быстро находить НОД многих чисел. Поэтому стражи решили изменить правила: теперь Витя должен найти наибольший общий делитель (НОД) чисел на промежутке [l; r], а стражи – наименьшее общее кратное (НОК), у кого получится число меньше, тот и выиграет.
Входные данные
Первая строка содержит количество элементов в массивеn (1 ≤ n ≤ 106). Во второй строке находится n чисел – элементы ai (1 ≤ ai ≤ 109) массива. В третьей строке находится количество запросовm (1 ≤ m ≤ 105). Далее в m строках находится по три числа q, l, r (1 ≤ l ≤ r ≤ n). Если q = 1, требуется определить победителя для промежутка [l; r], если q = 2, то нужно заменить элемент в позиции l на число r.
Выходные данные
Для каждого запроса с номером 1 в отдельной строке выведите строку «wins«, если Витя выиграл, строку «loser«, если он проиграл и «draw«, если была ничья.
Решение
В данной задаче нам нужно реализовать дерево отрезков, но поменять функцию которую определяет значение в узлах. Прочитав условие можно понять, что ответ «loser» мы не выведем никогда, так как НОД не может быть больше НОК. Тогда остается определить когда выводить «wins» или «draw». НОД и НОК некоторого количества чисел равны тогда и только тогда, когда все числы для которых мы считаем НОД и НОК равны между собой. Поэтому ассоциативной функцией для построения дерева выберем функцию равенства, если числа равны возвращаем само число, иначе 0. Тогда для ответа на вопрос задачи просто следует узнать что находится в соответсвующем узле.
Если это 0, то НОК больше НОД, иначе они равны и мы выведем «draw».
Код
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
#include <iostream> #include <algorithm> using namespace std; int equality(int a, int b){ return a == b ? a : 0; } void build(int *a, int *tr, int v, int l, int r) { if (l == r) { tr[v] = a[l]; } else { int middle = (l + r) / 2; build(a, tr, 2 * v, l, middle); build(a, tr, 2 * v + 1, middle + 1, r); tr[v] = equality(tr[2 * v], tr[2 * v + 1]); } } void update(int *tr, int v, int l, int r, int pos, int val) { if (l == r) { tr[v] = val; } else { int middle = (l + r) / 2; if (pos <= middle) { update(tr, 2 * v, l, middle, pos, val); } else { update(tr, 2 * v + 1, middle + 1, r, pos, val); } tr[v] = equality(tr[2 * v], tr[2 * v + 1]); } } int getEquality(int *tr, int v, int l, int r, int left, int right) { if (l == left && r == right) { return tr[v]; } int middle = (l + r) / 2; if (right <= middle) { return getEquality(tr, 2 * v, l, middle, left, right); } else if (left >= middle + 1) { return getEquality(tr, 2 * v + 1, middle + 1, r, left, right); } else { return equality(getEquality(tr, 2 * v, l, middle, left, middle), getEquality(tr, 2 * v + 1, middle + 1, r, middle + 1, right)); } } int main() { int n; cin >> n; int *a = new int[n]; for (int i = 0; i < n; i++) { cin >> a[i]; } int *tr = new int[4 * n]; build(a, tr, 1, 0, n - 1); int m; cin >> m; for (int i = 0; i < m; i++) { int q, l, r; cin >> q >> l >> r; if (q == 1) { cout << (getEquality(tr, 1, 0, n - 1, l - 1, r - 1) != 0 ? "draw" : "wins") << endl; } else if (q == 2) { update(tr, 1, 0, n - 1, l - 1, r); } } return 0; } |
Тесты
| Входные данные | Выходные данные |
| 5 2 4 6 10 8 6 1 1 5 1 2 3 2 5 15 2 3 10 1 3 5 1 1 1 |
wins wins wins draw |
| 5 7 7 7 7 7 4 1 1 5 2 2 1 1 1 5 1 3 5 |
draw wins draw |
Задача взята отсюда.
Решенная задача на e-olymp.