Redaksiya

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 $S e g T ree$ 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 $a_{i} \leq 1 0^{9}$ , the values in the cells of $S e g T ree$ will not exceed the limits of the $in t$ type.

vector<int> SegTree, v;

Build a segment tree based on the array $a$ .

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 $[l e f t, r i g h t]$ .

The vertex $v$ corresponds to the segment $[lp os, r p os]$ .

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 $v a l$ to the element at index $p os$ .

The vertex $v$ corresponds to the segment $[lp os, r 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]);
  }
}

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 $S e g T ree$ 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 $a$ .

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 $[l e f t, r i g h t]$ .

The vertex $v$ corresponds to the segment $[lp os, r p os]$ .

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 $v a l$ to the element at index $p os$ .

The vertex $v$ corresponds to the segment $[lp os, r p os]$ .

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)