Xətti şəbəkə#10455

Xətti şəbəkə (Həll təhlili)

Kompüterlər $1$ -dən $n$ -ə qədər nömrələnib. Çünki $n \leq 1 0^{9}$ n \le 10^9, işləyən və xarab olan kompüterlərin vəziyyəti haqqında məlumatı $ma p < in t, in t > m$ map<int, int> m xəritəsində saxlayacağıq. Əgər $m [i] = 0$ m[i] = 0 olarsa, deməli $i$ nömrəli kompüter işləyir, və $m [i] = 1$ m[i] = 1 olarsa, o xarabdır. Əvvəlcə bütün $1 \leq i \leq n$ 1 \le i \le n üçün $m [i] = 0$ m[i] = 0 deyək.

Asanlıq üçün $0$ və $n + 1$ n + 1 nömrəli iki uydurma xarab kompüter daxil edək. Onlar üçün $m [0] = m [n + 1] = 1$ m[0] = m[n + 1] = 1 olsun.

Şəbəkədə kompüter qruplarının sayını $c n t$ dəyişəni ilə saxlayacağıq. Əvvəlcə şəbəkədə bir qrup var, ona görə $c n t = 1$ cnt = 1 qoyaq.

İndi $q$ sorğuların işlənmə prosesini nəzərdən keçirək. Xüsusilə, $l$ nömrəli bir kompüterin xarab olma halını ( $t = 1$ t = 1 tipli sorğu):

Əgər $l$ kompüterin sağında və solunda xarab kompüterlər varsa, o zaman qrupların sayı $1$ azalır. Bu, əvvəllər yalnız bir cihazdan ibarət bir qrup olan $l$ kompüterinin xarab olması ilə bağlıdır.

Əgər $l$ kompüterin sağında və solunda işləyən kompüterlər varsa, qrupların sayı $1$ artacaq.

Bütün digər hallarda qrupların sayı dəyişməz qalır.

$t = 2$ t = 2 tipli sorğunun işlənməsi üçün cari $c n t$ dəyişəninin dəyərini çıxmaq kifayətdir.

Misal

Alqoritmin reallaşdırılması

map məlumat strukturunu elan edək.

map<int, int> m;

Kompüterlərin sayını $n$ və sorğuların sayını $q$ oxuyaq.

scanf("%d %d", &n, &q);

$0$ və $n + 1$ n + 1 nömrəli uydurma kompüterlərini başlat.

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

Şəbəkədə kompüter qruplarının sayını $c n t$ dəyişən ilə idarə edəcəyik. Əvvəldə bütün kompüterlər işləyir, belə ki, $c n t = 1$ cnt = 1.

cnt = 1;

$q$ sorğularını ardıcıl olaraq işlə.

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

Sorğu $t = 1$ t = 1. $l$ nömrəli kompüter xarab olur. Əgər $l$ kompüter artıq xarabdırsa, heç bir əməliyyat lazım deyil.

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

Müxtəlif halda, $l$ kompüterinin vəziyyətini xarab olaraq təyin edirik.

      m[l] = 1;

$l$ kompüterinin qonşularının (işləyən və ya xarab olan) vəziyyətinə əsasən, qrupların sayını yenidən hesablayırıq:

Əgər hər iki qonşu kompüteri xarabdırlarsa, $c n t$ $1$ -ə azalır;
Əgər hər iki qonşu kompüteri işləyirlərsə, $c n t$ $1$ -ə artır;

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

$t = 2$ t = 2 tipli sorğu üçün şəbəkədə cari kompüter qruplarının sayını çıxırıq.

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