Öyrənilməmiş dərslər ölkəsində 2#4482

Öyrənilməmiş dərslər ölkəsində 2 (Həll təhlili)

Müsbət ədədlər dəstəsinin ən böyük ortaq böləni (EBOB) həmişə onların ən kiçik ortaq vuruğundan (EKOV) kiçik və ya bərabərdir. Və bərabərlik yalnız dəstədəki bütün ədədlər eyni olduqda əldə edilir. Buna görə, məsələdə hər bir sorğu üçün müəyyən bir intervaldakı bütün ədədlərin bərabər olub olmadığını səmərəli şəkildə yoxlamaq lazımdır.

Məsələnin həlli üçün bir elementi modifikasiya edən və bir intervalda minimum və maksimum hesablayan intervallar ağacını həyata keçirmək kifayətdir. Bir intervaldakı ədədlər yalnız o zaman bərabər olacaq ki, onların minimumu maksimumuna bərabər olsun.

Algoritmin həyata keçirilməsi

$S e g T r ee$ SegTree strukturlar massivini elan edəcəyik - minimum və maksimum əməliyyatlarını dəstəkləyən intervallar ağacı. Daxil olan ədədlər ardıcıllığını $v$ massivində saxlayırıq.

#define INF 2000000000

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

C++

BuildTree funksiyası $a$ massivindən intervallar ağacını qurur.

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 funksiyası $[l e f t, r i g h t]$ [left, right] intervalında minimumu qaytarır.

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 funksiyası $[l e f t, r i g h t]$ [left, right] intervalında maksimumu qaytarır.

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 funksiyası bir elementi modifikasiya edir. $p os$ mövqeyinə $v a l$ elementi yazılır.

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

Proqramın əsas hissəsi. İlk indeksdən başlayaraq $v$ massivinə daxil olan ədədlər ardıcıllığını oxuyuruq.

scanf("%d", &n);
v.resize(n + 1);
for (i = 1; i <= n; i++)
  scanf("%d", &v[i]);

Intervallar ağacını $v [1.. n]$ massivinin elementləri ilə qururuq.

SegTree.resize(4 * n);
BuildTree(v,1,1,n);

Ardıcıl olaraq $m$ sorğunu işləyirik.

scanf("%d",&m);
for(i = 0; i < m; i++)
{
  scanf("%d %d %d",&q,&l,&r);

Əgər $q = 1$ q = 1 olduğu halda, $[l; r]$ [l; r] intervalında minimumu və maksimumu tapırıq. Əgər onlar bərabərdirsə, o zaman göstərilmiş intervaldakı ədədlərin EBOB və EKOV-ları eynidir. Oyunun nəticəsi bərabərlikdir. Əks halda, Vitya qalib gəlir.

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