У країні невивчених уроків 2#4482

У країні невивчених уроків 2 (Розбір)

Найбільший спільний дільник (НСД) набору додатних чисел завжди менше або дорівнює їх найменшому загальному кратному (НЗК). Причому рівність досягається лише у випадку, якщо всі числа в наборі однакові. Тому в задачі для кожного запиту потрібно ефективно перевірити, чи всі числа на заданому відрізку рівні.

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

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

Оголосимо масив структур $S e g T r ee$ SegTree — дерево відрізків, яке підтримує операції обчислення мінімуму та максимуму. Вхідну послідовність чисел зберігаємо в масиві $v$ .

#define INF 2000000000

struct node
{
  int min, max;
};
vector<node> SegTree;
vector<int> v;

C++

Функція 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);
  }
}

C++

Функція GetMin повертає мінімум на відрізку $[l e f t, r i g h t]$ [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));
}

C++

Функція GetMax повертає максимум на відрізку $[l e f t, r i g h t]$ [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));
}

C++

Функція Update здійснює модифікацію одного елемента. В позицію $p os$ записується елемент $v a l$ .

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

C++

Основна частина програми. Читаємо вхідну послідовність чисел у масив $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$ q = 1 знаходимо мінімум і максимум на відрізку $[l; r]$ [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);
}

C++