4482. В стране невыученных уроков - 2

 

 Теперь у Вити есть программа, которая помогает ему быстро находить наибольший общий делитель (НОД) многих чисел. Однако стражи решили усложнить задачу: теперь Витя должен находить НОД чисел на отрезке [l; r], а стражи – наименьшее общее кратное (НОК) тех же чисел. Победителем становится тот, у кого получится меньшее число.

 

Вход.  Первая строка содержит количество элементов в массиве n (1 ≤ n ≤ 106).

Вторая строка содержит n чисел – элементы массива ai (1 ≤ ai ≤ 109).

Третья строка содержит количество запросов m (1 ≤ m ≤ 105).

Каждая из следующих m строк содержит три числа q, l, r (1 ≤ l ≤ r ≤ n):

·        Если q = 1, требуется определить победителя для отрезка [l; r];

·        Если q = 2, следует заменить элемент массива на позиции l числом r.

 

Выход. Для каждого запроса с q = 1 выведите в отдельной строке:

·        “wins”, если Витя выиграл;

·        “loser”, если Витя проиграл;

·        “draw”, если произошла ничья.

 

Пример входа

Пример выхода

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

 

 

РЕШЕНИЕ

структуры данных - дерево отрезков, единичная модификация

 

Анализ алгоритма

Наибольший общий делитель (НОД) набора положительных чисел всегда меньше либо равен их наименьшему общему кратному (НОК). Причем равенство достигается только в случае, если все числа в наборе одинаковы. Поэтому в задаче для каждого запроса необходимо эффективно проверять, равны ли все числа на заданном отрезке.

Для решения задачи достаточно реализовать дерево отрезков, которое поддерживает модификацию одного элемента и вычисление минимума и максимума на отрезке. Числа на отрезке будут одинаковыми только тогда, когда минимум среди них равен максимуму.

 

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

Объявим массив структур SegTree – дерево отрезков, которое поддерживает операции вычисления минимума и максимума. Входную последовательность чисел храним в массиве v.

 

#define INF 2000000000

 

struct node

{

  int min, max;

};

vector<node> SegTree;

vector<int> v;

 

Функция BuidTree по массиву а строит дерево отрезков.

 

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

  }

}

 

Функция GetMin возвращает минимум на отрезке [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));

}

 

Функция GetMax возвращает максимум на отрезке [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));

}

 

Функция Update производит модификацию одного элемента. В позицию pos записывается элемент val.

 

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

  }

}

 

Основная часть программы. Читаем входную последовательность чисел в массив v, начиная с первого индекса.

 

scanf("%d", &n);

v.resize(n + 1);

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

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

 

Строим дерево отрезков по элементам массива v[1..n].

 

SegTree.resize(4 * n);

BuildTree(v,1,1,n);

 

Последовательно обрабатываем m запросов.

 

scanf("%d",&m);

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

{

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

 

При q = 1 находим минимум и максимум на отрезке [l; r]. Если они равны, то НОД и НОК чисел указанного отрезка одинаковы. Результатом игры является ничья. Иначе Витя выигрывает.

 

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

}