4481. In the country of unlearned lessons

 

Victor found himself in a land of unlearned lessons. To return home, he must complete various tasks. One such task involves defeating a guard in a GCD game. The rules are straightforward: given an array of positive integers, the players select two numbers l and r, and find the greatest common divisor (GCD) of all the elements in the array from index l to r inclusive. The player who finds the GCD the fastest wins. To prevent unfair play, some numbers in the array may be replaced occasionally.

Victor is eager to return home. Help him by writing a program that can quickly calculate the GCD over a specified interval.

 

Input. The first line contains the number of elements n (1 ≤ n ≤ 105) in array. The second line contains n integers – the elements ai (1 ≤ ai ≤ 109) of array. The third line gives the number of queries m (1 ≤ m ≤ 105). Each of the next m lines contains three integers q, l, r (1 ≤ l ≤ r ≤ n).

·        If q = 1, find the GCD of elements on an interval [l, r];

·        If q = 2, change the element at position l to number r.

 

Output. For each query with number 1 print the answer on a separate line.

 

Sample input

Sample output

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

 

 

SOLUTION

segment tree, single modification

 

Algorithm analysis

To solve the problem, it is necessary to implement a segment tree that supports modification of a single element and computation of the Greatest Common Divisor (GCD) over a segment.

 

Algorithm realization

Let’s declare an array SegTree to store the segment tree. We’ll store the input sequence of numbers in the array v. The segment tree supports the GCD operation. Since ai ≤ 109, the values in the cells of SegTree will not exceed the limits of the int type.

 

vector<int> SegTree, v;

 

Build a segment tree based on the array à.

 

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

  }

}

 

The GetGCD function returns the GCD over the segment [left, right].

The vertex v corresponds to the segment [lpos, rpos].

 

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

}

 

The Update function assigns the value val to the element at index pos.

The vertex v corresponds to the segment [lpos, rpos].

 

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

  }

}

 

The main part of the program. Read the input sequence of numbers into the array v, starting from the first index.

 

scanf("%d", &n);

v.resize(n + 1);

for (i = 1; i <= n; i++)

  scanf("%d", &v[i]);

 

Build the segment tree based on the elements of the array v[1 … n].

 

SegTree.resize(4 * n);

BuildTree(v,1,1,n);

 

Process the queries sequentially.

 

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

}

 

Python realization

In the list SegTree store a segment tree. We’ll implement a segment tree that supports the GCD operation.

 

import math

 

Declare a function gcd that computes the GCD of two numbers.

 

def gcd(a, b):

  return math.gcd(a, b)

 

Build a segment tree based on the list à.

 

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

 

The GetGCD function returns the GCD over the segment [left, right].

The vertex v corresponds to the segment [lpos, rpos].

 

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

 

The Update function assigns the value val to the element at index pos.

The vertex v corresponds to the segment [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])

 

The main part of the program. Read the input sequence of numbers into the list v, starting from the first index.

 

n = int(input())

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

 

Build the segment tree based on the elements of the list v[1 … n].

 

SegTree = [0] * (4 * n)

BuildTree(v, 1, 1, n)

 

Process the queries sequentially.

 

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)