Öyrənilməmiş dərslər ölkəsində#4481

Öyrənilməmiş dərslər ölkəsində (Həll təhlili)

Məsələni həll etmək üçün iki növ sorğunu emal etmək lazımdır:

seqment üzərindəki elementlərin ən böyük ortaq böləninin (ƏBOB) hesablanması;
massivin bir elementinin dəyişdirilməsi.

ƏBOB-un əsas xüsusiyyəti onun assosiativliyidir: bir neçə ədədin ƏBOB-u hissələr şəklində hesablana bilər. Əgər $[l, r]$ [l, r] seqmenti iki hissəyə — $[l, k]$ [l, k] və $[k + 1, r]$ [k + 1, r] — bölünərsə, onda

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))

Məhz bu cür əməliyyat üçün seqment ağacı nəzərdə tutulmuşdur. Hər bir təpə öz seqmentinin elementlərinin ƏBOB-unu saxlayır, daxili təpədəki dəyər isə onun iki övladının dəyərlərinin ƏBOB-una bərabərdir. Seqment ağacı həm seqment üzərində ƏBOB-un hesablanmasına, həm də massiv elementinin dəyişdirilməsinə $O (lo g n)$ O(\log n) ƏBOB əməliyyatı sərf olunmaqla imkan verir.

Misal

Alqoritmin misal üzərində necə işlədiyinə baxaq. Soldakı şəkildə ilkin $(2, 4, 6, 10, 8)$ (2, 4, 6, 10, 8) massivi üçün seqment ağacı göstərilmişdir. Hər bir təpədə onun seqmenti və bu seqmentin elementlərinin ƏBOB-u göstərilir. Sağdakı şəkildə isə hər iki dəyişdirmə sorğusu icra edildikdən sonrakı ağac göstərilir; dəyəri dəyişmiş təpələr xüsusi işarələnmişdir.

Sorğuları bir-bir emal edək:

$115$ : $[1, 5]$ seqmenti kökün seqmenti ilə üst-üstə düşür, buna görə cavab kökdə saxlanılır və $2$ -yə bərabərdir;
$123$ : $[2, 3]$ seqmenti $[2]$ və $[3]$ hissələrinə bölünür, cavab $GCD (4, 6) = 2$ \mathrm{GCD}(4, 6) = 2-dir;
$2515$ : $a_{5}$ a_5 elementi $15$ olur. $[5]$ yarpağından kökə qədər olan yol üzərindəki təpələr yenidən hesablanır: $[4, 5]$ təpəsində $GCD (10, 15) = 5$ \mathrm{GCD}(10, 15) = 5, kökdə isə — $GCD (2, 5) = 1$ \mathrm{GCD}(2, 5) = 1 alınır;
$2310$ : $a_{3}$ a_3 elementi $10$ olur. $[1, 3]$ təpəsində $GCD (2, 10) = 2$ \mathrm{GCD}(2, 10) = 2, kökdə isə — $GCD (2, 5) = 1$ \mathrm{GCD}(2, 5) = 1 alınır;
$135$ : $[3, 5]$ seqmenti $[3]$ və $[4, 5]$ hissələrinə bölünür, cavab $GCD (10, 5) = 5$ \mathrm{GCD}(10, 5) = 5-dir;
$115$ : cavab kökdə saxlanılır və $1$ -ə bərabərdir.

Biz $2, 2, 5, 1$ 2, 2, 5, 1 cavablarını alırıq ki, bu da misaldakı cavabla üst-üstə düşür.

Alqoritmin realizasiyası

Seqment ağacını saxlamaq üçün $S e g T r ee$ SegTree massivini, giriş ədədlər ardıcıllığını saxlamaq üçün isə $v$ massivini elan edək. Ağacın hər bir təpəsi öz seqmentinin elementlərinin ƏBOB-unu saxlayır. $a_{i} \leq 1 0^{9}$ a_i \le 10^9 olduğundan və ƏBOB öz arqumentlərindən böyük olmadığından, $S e g T r ee$ SegTree-nin xanalarındakı dəyərlər int tipinin hüdudlarından kənara çıxmır.

vector<int> SegTree, v;

BuildTree funksiyası $a$ massivindən seqment ağacını qurur. $v$ təpəsi $[l p os, r p os]$ [lpos, rpos] seqmentinə uyğun gəlir. İki ədədin ƏBOB-unu hesablamaq üçün standart $g c d$ funksiyasından istifadə olunur.

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 funksiyası $[l e f t, r i g h t]$ [left, right] seqmenti üzərindəki elementlərin ƏBOB-unu qaytarır. $v$ təpəsi $[l p os, r p os]$ [lpos, rpos] seqmentinə uyğun gəlir.

Əgər sorğu seqmenti boşdursa ( $l e f t > r i g h t$ left > right), $0$ qaytarılır — ƏBOB əməliyyatı üçün neytral element. Əgər sorğu seqmenti təpənin seqmenti ilə üst-üstə düşürsə, cavab $S e g T r ee [v]$ SegTree[v]-də saxlanılır. Əks halda, sorğu sol və sağ övladlara düşən hissələrə bölünür və nəticələrin ƏBOB-u qaytarılır.

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 funksiyası $p os$ indeksli elementə $v a l$ dəyərini mənimsədir. $v$ təpəsi $[l p os, r p os]$ [lpos, rpos] seqmentinə uyğun gəlir.

$p os$ mövqeyinə uyğun yarpağa enmək və ona yeni dəyəri yazmaq lazımdır. Rekursiyadan qayıdarkən yarpaqdan kökə qədər olan yol üzərindəki bütün təpələrdə ƏBOB yenidən hesablanır.

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++

Proqramın əsas hissəsi. Giriş ədədlər ardıcıllığını $1$ -ci indeksdən başlayaraq $v$ massivinə oxuyuruq.

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] massivinin elementlərindən seqment ağacını qururuq. $n$ elementdən ibarət seqment ağacı üçün ən çoxu $4 n$ xana lazımdır.

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

Sorğuları bir-bir emal edirik. Əgər $q = 1$ q = 1 olarsa, $[l, r]$ [l, r] seqmenti üzərindəki ƏBOB-u çap edirik. Əgər $q = 2$ q = 2 olarsa, $l$ indeksli elementə $r$ dəyərini mənimsədirik.

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 üzərində realizasiya

$S e g T r ee$ SegTree siyahısı seqment ağacını saxlayır; onun hər bir təpəsi öz seqmentinin elementlərinin ƏBOB-unu özündə saxlayır. ƏBOB-un hesablanması üçün funksiya daxil olan $ma t h$ modulunu idxal edirik.

import math

İki ədədin ƏBOB-unu hesablayan gcd funksiyasını elan edək.

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

BuildTree funksiyası $a$ siyahısından seqment ağacını qurur. $v$ təpəsi $[l p os, r p os]$ [lpos, rpos] seqmentinə uyğun gəlir.

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

GetGCD funksiyası $[l e f t, r i g h t]$ [left, right] seqmenti üzərindəki elementlərin ƏBOB-unu qaytarır. $v$ təpəsi $[l p os, r p os]$ [lpos, rpos] seqmentinə uyğun gəlir.

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 funksiyası $p os$ indeksli elementə $v a l$ dəyərini mənimsədir. $v$ təpəsi $[l p os, r p os]$ [lpos, rpos] seqmentinə uyğun gəlir.

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

Proqramın əsas hissəsi. Giriş ədədlər ardıcıllığını $1$ -ci indeksdən başlayaraq $v$ siyahısına oxuyuruq.

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

$v [1 \dots n]$ v[1 \ldots n] siyahısının elementlərindən seqment ağacını qururuq. $n$ elementdən ibarət seqment ağacı üçün ən çoxu $4 n$ xana lazımdır.

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

Sorğuları bir-bir emal edirik. Əgər $q = 1$ q = 1 olarsa, $[l, r]$ [l, r] seqmenti üzərindəki ƏBOB-u çap edirik; əgər $q = 2$ q = 2 olarsa, $l$ indeksli elementə $r$ dəyərini mənimsədirik.

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