Задача
Витя попал в страну невыученных уроков. Для того, чтобы вернуться домой ему нужно выполнить множество заданий. В этой задаче он должен выиграть у стражей в НОД-игру. Правила этой игры очень простые: есть массив натуральных чисел, после чего игроки выбирают два числа [latex]l[/latex] и [latex]r[/latex], и им надо посчитать наибольший общий делитель (НОД) всех элементов в массиве с индексами от [latex]l[/latex] до [latex]r[/latex] включительно. Кто быстрее посчитает, тот и выиграл. Чтобы избежать нечестных игр, они иногда заменяют некоторые числа в массиве на другие.
Витя очень хочет домой, помогите ему в этом, для чего напишите программу, которая будет очень быстро считать НОД на заданном промежутке.
Входные данные
Первая строка содержит количество элементов [latex]n[/latex] [latex](1\leq n\leq 10^5)[/latex] в массиве. Во второй строке находится [latex]n[/latex] чисел – элементы [latex]a_i[/latex] [latex](1\leq a_i\leq 10^9)[/latex] массива. В третьей строке находится количество запросов [latex]m[/latex] [latex](1\leq m\leq 10^5)[/latex]. Далее в [latex]m[/latex] строках находятся по три числа [latex]q[/latex], [latex]l[/latex], [latex]r[/latex] [latex](1\leq l\leq r\leq n)[/latex]. Если [latex]q=1[/latex], требуется посчитать НОД элементов на промежутке [latex][l,r][/latex], если [latex]q=2[/latex], то надо заменить элемент в позиции [latex]l[/latex] на число [latex]r[/latex].
Выходные данные
Для каждого запроса с номером [latex]l[/latex] в отдельной строке выведите ответ на запрос.
Тесты
| Входные данные: | Выходные данные: |
| 5 2 4 6 10 8 6 1 1 5 1 2 3 2 5 15 2 3 10 1 3 5 1 1 5 |
2 2 5 1 |
Код программы
|
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 |
#include <iostream> #include <vector> using namespace std; vector<int> tree; int n; int gcd (int a, int b){ if (a == 0) return b; return gcd(b % a, a); } void build(int a[], int v = 1, int tl = 0, int tr = n - 1){ if(tl == tr){ tree[v] = a[tl]; }else{ int middle = (tl + tr) / 2; build(a, v * 2, tl, middle); build(a, v * 2 + 1, middle + 1, tr); tree[v] = gcd(tree[v * 2], tree[v * 2 + 1]); } } int get(int a[], int l, int r, int v = 1, int tl = 0, int tr = n-1){ if(l > r){ return 0; } if(tl == l && tr == r){ return tree[v]; } int middle = (tl + tr) / 2; int L = get(a, l, min(middle, r), v * 2, tl, middle); int R = get(a, max(middle + 1, l), r, v*2 + 1, middle + 1, tr); return gcd(L, R); } void update(int pos, int val, int v = 1, int tl = 0, int tr = n - 1){ if(tl == tr){ tree[v] = val; }else{ int middle = (tl + tr) / 2; if(pos <= middle){ update(pos, val, v * 2, tl, middle); }else{ update(pos, val, v * 2 + 1, middle + 1, tr); } tree[v] = gcd(tree[v * 2], tree[v * 2 + 1]); } } int main(){ cin >> n; int a[n]; for (int i = 0; i < n; i++){ cin >> a[i]; } tree.resize(4 * n); build(a); int m, l, r, q; cin >> m; while (m--){ cin >> q >> l >> r; if (q == 1){ cout << get(a, l - 1, r - 1) << endl; } else{ update(l - 1, r); } } return 0; } |
Алгоритм решения
Данная задача решена с помощью структуры данных «дерево отрезков». В каждой вершине дерева храним НОД всех чисел на соответствующем отрезке массива. Функции, отвечающие за построение самого дерева отрезков, нахождение НОД на отрезке и запрос на модификацию элемента являются рекурсивными. Дерево строим следующим образом: листьями данного дерева будут сами элементы исходного массива, а значения элементов, находящихся на уровень выше, будут представлять собой НОД двух соседних листов. Таким же образом считаем значения вершин следующего уровня и т.д. Чтобы найти НОД на заданном отрезке рассматриваем случаи расположения данного отрезка. Он может полностью принадлежать одному потомку, а может быть разбит между правым и левым потомками. В первом случае функцию запускаем от одного потомка и получаем требуемое, во втором случае функцию запускаем от двух потомков и находим от полученных результатов НОД. При выполнении запроса на модификацию запускаем функцию от корня, спускаемся до требуемого элемента, изменяем его, и поднимаемся обратно к корню, модифицируя значения вершин, для которых данный элемент является подотрезком.
В самой задаче, в зависимости от требуемого, в цикле находим НОД на заданном отрезке или выполняем модификацию элемента.
Для получения подробной информации о структуре данных «Дерево отрезков» можно перейти по данной ссылке
Ссылка на засчитанное решение на e-olymp
Ссылка на условие задачи
Ссылка на решение задачи на ideone.com