4482. In the country of unlearned lessons - 2

 

Now, Vitya has a program that helps him quickly find the greatest common divisor (GCD) of many numbers. However, the guards decided to make the task more challenging: Vitya must calculate the GCD of the numbers on a segment [l; r], while the guards calculate the least common multiple (LCM) of the same numbers. The winner is the one whose result is smaller.

 

Input.  The first line contains the number of elements in the array n (1 ≤ n ≤ 106).

The second line contains n numbers – the elements of the array ai (1 ≤ ai ≤ 109).

The third line specifies the number of queries m (1 ≤ m ≤ 105).

Each of the following m lines contains three integers q, l, r (1 ≤ l ≤ r ≤ n):

·        If q = 1, determine the winner for the segment [l; r];

·        If q = 2, replace the element at position l with the number r.

 

Output. For each query with q = 1, print the result in a separate line:

·        “wins” if Vitya wins;

·        “loser”  if Vitya loses;

·        “draw” if it’s a tie.

 

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 1

wins

wins

wins

draw

 

 

SOLUTION

segment tree, single modification

 

Algorithm analysis

The greatest common divisor (GCD) of a set of positive numbers is always less than or equal to their least common multiple (LCM). Equality is achieved only if all the numbers in the set are identical. Therefore, for each query in the problem, it is necessary to efficiently check whether all the numbers in the specified segment are equal.

To solve this problem, it is sufficient to implement a segment tree that supports single-element modification and the computation of the minimum and maximum values on a segment. The numbers in the segment will be equal only if the minimum and maximum among them are the same.

 

Algorithm implementation

Declare an array of structures SegTree, representing a segment tree that supports minimum and maximum operations. The input sequence of numbers is stored in the array v.

 

#define INF 2000000000

 

struct node

{

  int min, max;

};

vector<node> SegTree;

vector<int> v;

 

The function BuidTree constructs the segment tree based on the array a.

 

void BuildTree(vector<int> &a, int v, int lpos, int rpos)

{

  if (lpos == rpos)

    SegTree[v].min = SegTree[v].max = a[lpos];

  else

  {

    int mid = (lpos + rpos) / 2;

    BuildTree(a, 2 * v, lpos, mid);

    BuildTree(a, 2 * v + 1, mid + 1, rpos);

 

    SegTree[v].min = min(SegTree[2 * v].min, SegTree[2 * v  + 1].min);

    SegTree[v].max = max(SegTree[2 * v].max, SegTree[2 * v  + 1].max);

  }

}

 

The GetMin function returns the minimum value on the segment [left, right].

 

int GetMin(int v, int lpos, int rpos, int left, int right)

{

  if (left > right) return INF;

  if ((left == lpos) && (right == rpos)) return SegTree[v].min;

  int mid = (lpos + rpos) / 2;

  return min(GetMin(2 * v, lpos, mid, left, min(right, mid)),

         GetMin(2 * v + 1, mid + 1, rpos, max(left, mid + 1), right));

}

 

The GetMax function returns the maximum value on the segment [left, right].

 

int GetMax(int v, int lpos, int rpos, int left, int right)

{

  if (left > right) return -INF;

  if ((left == lpos) && (right == rpos)) return SegTree[v].max;

  int mid = (lpos + rpos) / 2;

  return max(GetMax(2 * v, lpos, mid, left, min(right, mid)),

         GetMax(2 * v + 1, mid + 1, rpos, max(left, mid + 1), right));

}

 

The Update function modifies a single element: the value val is written at position pos.

 

void Update(int v, int lpos, int rpos, int pos, int val)

{

  if (lpos == rpos)

    SegTree[v].min = SegTree[v].max = 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].min = min(SegTree[2 * v].min, SegTree[2 * v + 1].min);

    SegTree[v].max = max(SegTree[2 * v].max, SegTree[2 * v + 1].max);

  }

}

 

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 a segment tree based on the elements of the array v[1..n].

 

SegTree.resize(4 * n);

BuildTree(v,1,1,n);

 

Sequentially process m queries.

 

scanf("%d",&m);

for(i = 0; i < m; i++)

{

  scanf("%d %d %d",&q,&l,&r); 

 

For q = 1 find the minimum and maximum on the segment [l; r]. If they are equal, the GCD and LCM of the numbers on the specified segment are the same, resulting in a draw. Otherwise, Vitya wins.

 

  if (q == 1)

  {

    int min = GetMin(1,1,n,l,r);

    int max = GetMax(1,1,n,l,r);

    if (min == max) printf("draw\n"); else printf("wins\n");

  }

  else Update(1,1,n,l,r);

}