У країні невивчених уроків (Розбір)

Для розв'язання задачі потрібно обробляти запити двох типів:

обчислення найбільшого спільного дільника (НСД) елементів на відрізку;
зміна одного елемента масиву.

Ключова властивість НСД — його асоціативність: НСД кількох чисел можна обчислювати частинами. Якщо відрізок $[l, r]$ [l, r] розбити на дві частини $[l, k]$ [l, k] та $[k + 1, r]$ [k + 1, r], то

GCD (a_{l}, \dots, a_{r}) = GCD (GCD (a_{l}, \dots, a_{k}), GCD (a_{k + 1}, \dots, a_{r}))

\mathrm{GCD}(a_l, \ldots, a_r) = \mathrm{GCD}(\mathrm{GCD}(a_l, \ldots, a_k), \mathrm{GCD}(a_{k+1}, \ldots, a_r))

Саме для такого роду операцій і призначене дерево відрізків. У кожній вершині зберігається НСД елементів її відрізка, а значення у внутрішній вершині дорівнює НСД значень її двох дітей. Дерево відрізків дозволяє як обчислювати НСД на відрізку, так і змінювати елемент масиву за допомогою $O (lo g n)$ O(\log n) операцій обчислення НСД.

Приклад

Розглянемо, як працює алгоритм на прикладі. На лівому малюнку показано дерево відрізків для початкового масиву $(2, 4, 6, 10, 8)$ (2, 4, 6, 10, 8). У кожній вершині вказано її відрізок та НСД елементів на ньому. На правому малюнку показано дерево після виконання обох запитів зміни; вершини, значення яких змінилися, виділено.

Обробимо запити по черзі:

$115$ : відрізок $[1, 5]$ збігається з відрізком кореня, тому відповідь зберігається в корені і дорівнює $2$ ;
$123$ : відрізок $[2, 3]$ розбивається на частини $[2]$ та $[3]$ , відповідь — $GCD (4, 6) = 2$ \mathrm{GCD}(4, 6) = 2;
$2515$ : елемент $a_{5}$ a_5 стає рівним $15$ . Перераховуються вершини на шляху від листка $[5]$ до кореня: у вершині $[4, 5]$ отримуємо $GCD (10, 15) = 5$ \mathrm{GCD}(10, 15) = 5, у корені — $GCD (2, 5) = 1$ \mathrm{GCD}(2, 5) = 1;
$2310$ : елемент $a_{3}$ a_3 стає рівним $10$ . У вершині $[1, 3]$ отримуємо $GCD (2, 10) = 2$ \mathrm{GCD}(2, 10) = 2, у корені — $GCD (2, 5) = 1$ \mathrm{GCD}(2, 5) = 1;
$135$ : відрізок $[3, 5]$ розбивається на частини $[3]$ та $[4, 5]$ , відповідь — $GCD (10, 5) = 5$ \mathrm{GCD}(10, 5) = 5;
$115$ : відповідь зберігається в корені і дорівнює $1$ .

Отримуємо відповіді $2, 2, 5, 1$ 2, 2, 5, 1, що збігаються з відповіддю з прикладу.

Реалізація алгоритму

Оголосимо масив $S e g T r ee$ SegTree для зберігання дерева відрізків та масив $v$ для зберігання вхідної послідовності чисел. У кожній вершині дерева зберігається НСД елементів її відрізка. Оскільки $a_{i} \leq 1 0^{9}$ a_i \le 10^9, а НСД не перевищує своїх аргументів, значення в комірках $S e g T r ee$ SegTree не виходять за межі типу int.

vector<int> SegTree, v;

Функція BuildTree будує дерево відрізків із масиву $a$ . Вершина $v$ відповідає відрізку $[l p os, r p os]$ [lpos, rpos]. Для обчислення НСД двох чисел використовується стандартна функція $g c d$ .

void BuildTree(vector<int> &a, int v, int lpos, int rpos)
{
  if (lpos == rpos) SegTree[v] = a[lpos];
  else
  {
    int mid = (lpos + rpos) / 2;
    BuildTree(a, 2 * v, lpos, mid);
    BuildTree(a, 2 * v + 1, mid + 1, rpos);
    SegTree[v] = gcd(SegTree[2 * v], SegTree[2 * v + 1]);
  }
}

C++

Функція GetGCD повертає НСД елементів на відрізку $[l e f t, r i g h t]$ [left, right]. Вершина $v$ відповідає відрізку $[l p os, r p os]$ [lpos, rpos].

Якщо запитуваний відрізок порожній ( $l e f t > r i g h t$ left > right), повертаємо $0$ — нейтральний елемент для операції НСД. Якщо запитуваний відрізок збігається з відрізком вершини, відповідь зберігається в $S e g T r ee [v]$ SegTree[v]. Інакше розбиваємо запит на частини, що потрапляють у лівого та правого дітей, і повертаємо НСД результатів.

int GetGCD(int v, int lpos, int rpos, int left, int right)
{
  if (left > right) return 0;
  if ((left == lpos) && (right == rpos)) return SegTree[v];
  int mid = (lpos + rpos) / 2;
  return gcd(GetGCD(2 * v, lpos, mid, left, min(right, mid)),
         GetGCD(2 * v + 1, mid + 1, rpos, max(left, mid + 1), right));
}

C++

Функція update присвоює значення $v a l$ елементу з індексом $p os$ . Вершина $v$ відповідає відрізку $[l p os, r p os]$ [lpos, rpos].

Спускаємося до листка, що відповідає позиції $p os$ , і записуємо в нього нове значення. При поверненні з рекурсії перераховуємо НСД у всіх вершинах на шляху від листка до кореня.

void update(int v, int lpos, int rpos, int pos, int val)
{
  if (lpos == rpos) SegTree[v] = val;
  else
  {
    int mid = (lpos + rpos) / 2;
    if (pos <= mid) update(2 * v, lpos, mid, pos, val);
    else update(2 * v + 1, mid + 1, rpos, pos, val);
    SegTree[v] = gcd(SegTree[2 * v], SegTree[2 * v + 1]);
  }
}

C++

Основна частина програми. Зчитуємо вхідну послідовність чисел у масив $v$ , починаючи з індексу $1$ .

scanf("%d", &n);
v.resize(n + 1);
for (i = 1; i <= n; i++)
  scanf("%d", &v[i]);

Будуємо дерево відрізків з елементів масиву $v [1 \dots n]$ v[1 \ldots n]. Дереву відрізків на $n$ елементів потрібно не більше $4 n$ комірок.

SegTree.resize(4 * n);
BuildTree(v,1,1,n);

Обробляємо запити по черзі. Якщо $q = 1$ q = 1, виводимо НСД на відрізку $[l, r]$ [l, r]. Якщо $q = 2$ q = 2, присвоюємо значення $r$ елементу з індексом $l$ .

scanf("%d",&m);
for(i = 0; i < m; i++)
{
  scanf("%d %d %d",&q,&l,&r);
  if (q == 1) printf("%d\n",GetGCD(1,1,n,l,r));
  else update(1,1,n,l,r);
}

C++

Реалізація на Python

Список $S e g T r ee$ SegTree зберігає дерево відрізків; у кожній його вершині міститься НСД елементів її відрізка. Імпортуємо модуль $ma t h$ , який містить функцію обчислення НСД.

import math

Оголосимо функцію gcd, яка обчислює НСД двох чисел.

def gcd(a, b):
  return math.gcd(a, b)

Функція BuildTree будує дерево відрізків зі списку $a$ . Вершина $v$ відповідає відрізку $[l p os, r p os]$ [lpos, rpos].

def BuildTree(a, v, lpos, rpos):
  if lpos == rpos:
    SegTree[v] = a[lpos]
  else:
    mid = (lpos + rpos) // 2
    BuildTree(a, 2 * v, lpos, mid)
    BuildTree(a, 2 * v + 1, mid + 1, rpos)
    SegTree[v] = gcd(SegTree[2 * v], SegTree[2 * v + 1])

Python

def GetGCD(v, lpos, rpos, left, right):
  if left > right:
    return 0
  if left == lpos and right == rpos:
    return SegTree[v]
  mid = (lpos + rpos) // 2
  return gcd(GetGCD(2 * v, lpos, mid, left, min(right, mid)),
      GetGCD(2 * v + 1, mid + 1, rpos, max(left, mid + 1),right))

Python

Функція Update присвоює значення $v a l$ елементу з індексом $p os$ . Вершина $v$ відповідає відрізку $[l p os, r p os]$ [lpos, rpos].

def Update(v, lpos, rpos, pos, val):
  if lpos == rpos:
    SegTree[v] = val
  else:
    mid = (lpos + rpos) // 2
    if pos <= mid:
      Update(2 * v, lpos, mid, pos, val)
    else:
      Update(2 * v + 1, mid + 1, rpos, pos, val)
    SegTree[v] = gcd(SegTree[2 * v], SegTree[2 * v + 1])

Python

Основна частина програми. Зчитуємо вхідну послідовність чисел у список $v$ , починаючи з індексу $1$ .

n = int(input())
v = [0] + list(map(int, input().split()))

Будуємо дерево відрізків з елементів списку $v [1 \dots n]$ v[1 \ldots n]. Дереву відрізків на $n$ елементів потрібно не більше $4 n$ комірок.

SegTree = [0] * (4 * n)
BuildTree(v, 1, 1, n)

Обробляємо запити по черзі. Якщо $q = 1$ q = 1, виводимо НСД на відрізку $[l, r]$ [l, r]; якщо $q = 2$ q = 2, присвоюємо значення $r$ елементу з індексом $l$ .

m = int(input())
for _ in range(m):
  q, l, r = map(int, input().split())
  if q == 1:
    print(GetGCD(1, 1, n, l, r))
  else:
    Update(1, 1, n, l, r)

Python