Лінійна мережа#10455

Лінійна мережа (Розбір)

Комп'ютери пронумеровані числами від $1$ до $n$ . Оскільки $n \leq 1 0^{9}$ n \le 10^9, інформацію про стан робочих і несправних комп'ютерів будемо зберігати у відображенні $ma p ⟨ in t, in t ⟩ m$ map\langle int, int \rangle m. Значення $m [i] = 0$ m[i] = 0, якщо комп'ютер з номером $i$ працює, і $m [i] = 1$ m[i] = 1, якщо він зламаний. Спочатку для всіх $1 \leq i \leq n$ 1 \le i \le n покладемо $m [i] = 0$ m[i] = 0.

Для зручності введемо два фіктивних зламаних комп'ютери з номерами $0$ та $n + 1$ n + 1. Задамо значення $m [0] = m [n + 1] = 1$ m[0] = m[n + 1] = 1.

Кількість груп комп'ютерів у мережі будемо підтримувати у змінній $c n t$ . Спочатку в мережі є одна група, тому покладемо $c n t = 1$ cnt = 1.

Тепер розглянемо процес обробки $q$ запитів. Зокрема, розберемо поломку комп'ютера з номером $l$ (запит типу $t = 1$ t = 1):

Якщо як справа, так і зліва від комп'ютера $l$ знаходяться зламані комп'ютери, то кількість груп зменшується на $1$ . Це пов'язано з тим, що комп'ютер $l$ , який раніше представляв групу з одного пристрою, виходить з ладу.

Якщо справа і зліва від комп'ютера $l$ знаходяться робочі комп'ютери, то кількість груп збільшиться на $1$ .

У всіх інших випадках кількість груп залишається незмінною.

Для обробки запиту типу $t = 2$ t = 2 достатньо вивести поточне значення змінної $c n t$ .

Приклад

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

Оголосимо структуру даних map.

map\langle int, int \rangle m;

Читаємо кількість комп'ютерів $n$ і кількість запитів $q$ .

scanf("%d %d", \u0026n, \u0026q);

Ініціалізуємо фіктивні комп'ютери з номерами $0$ і $n + 1$ n + 1.

m[0] = 1;
m[n + 1] = 1;

Кількість груп комп'ютерів у мережі будемо підтримувати у змінній $c n t$ . Спочатку всі комп'ютери робочі, тому $c n t = 1$ cnt = 1.

cnt = 1;

Послідовно обробляємо $q$ запитів.

while (q--)
{
  scanf("%d", \u0026t);
  if (t == 1)
  {

Запит $t = 1$ t = 1. Комп'ютер з номером $l$ виходить з ладу. Якщо комп'ютер $l$ вже був зламаний, ніяких дій не потрібно.

    scanf("%d", \u0026l);
    if (m[l] == 0)
    {

В протилежному випадку встановлюємо стан комп'ютера $l$ як зламане.

      m[l] = 1;

В залежності від стану сусідніх з $l$ комп'ютерів (робочих або зламаних) перераховуємо кількість груп:

Якщо обидва сусідніх комп'ютери зламані, то зменшуємо $c n t$ на $1$ ;
Якщо обидва сусідніх комп'ютери робочі, то збільшуємо $c n t$ на $1$ ;

      k = m[l - 1] + m[l + 1];
      if (k == 2) cnt--;
      else if (k == 0) cnt++;
    }
  }
  else

Для запиту $t = 2$ t = 2 виводимо поточну кількість груп комп'ютерів у мережі.

    printf("%d\n", cnt);
}