10455. Линейная сеть

 

В центре обработки больших данных была установлена линейная сеть, состоящая из n компьютеров. Все компьютеры пронумерованы последовательными целыми числами от 1 до n. Между любыми двумя компьютерами с соседними номерами имеется прямое соединение. Очевидно, что в такой сети можно обмениваться данными между любыми двумя компьютерами, напрямую или через промежуточные.

Однако из-за высокой нагрузки некоторые компьютеры могут выходить из строя. В таких случаях связь между некоторыми компьютерами прерывается, и передача данных между ними становится невозможной.

Вам необходимо определить текущее количество групп в сети. Под группой понимается максимальное множество активных компьютеров, в котором любые два компьютера соединены друг с другом напрямую или через другие компьютеры. Группа также может состоять из одного компьютера.

Вам предстоит ответить на q запросов. Каждый запрос либо сообщает о выходе из строя одного из компьютеров, либо запрашивает текущее количество групп.

 

Вход. Первая строка содержит два целых числа n (1 ≤ n ≤ 109) и q (1 ≤ q ≤ 105) – количество компьютеров и количество запросов соответственно. Каждая из следующих q строк представляет один запрос.

Каждый запрос начинается с числа T, обозначающего его тип. После T = 1 всегда следует номер L (1 ≤ L ≤ n) вышедшего из строя компьютера.

·       Запрос типа T = 1 указывает, что компьютер с номером L вышел из строя.

·       Запрос типа T = 2 требует вывести текущее количество групп в сети.

 

Выход. Для каждого запроса второго типа (T = 2) в отдельной строке выведите количество групп в сети на данный момент.

 

Пример входа

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

4 6

1 2

2

1 4

2

1 2

2

2

2

2

 

 

РЕШЕНИЕ

структура данных map

 

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

Компьютеры пронумерованы числами от 1 до n. Поскольку n ≤ 109, информацию о состоянии рабочих и вышедших из строя компьютеров будем хранить в отображении map<int, int> m. Значение m[i] = 0, если компьютер с номером i работает, и m[i] = 1, если он сломан. Изначально для всех 1 ≤ i ≤ n положим m[i] = 0.

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

Количество групп компьютеров в сети будем поддерживать в переменной cnt. Изначально в сети имеется одна группа, поэтому положим cnt = 1.

 

Теперь рассмотрим процесс обработки q запросов. В частности, разберем поломку компьютера с номером l (запрос типа t = 1):

·        Если как справа, так и слева от компьютера l находятся сломанные компьютеры, то количество групп уменьшается на 1. Это связано с тем, что компьютер l, который ранее представлял группу из одного устройства, выходит из строя.

 

·        Если справа и слева от компьютера l находятся рабочие компьютеры, то количество групп увеличится на 1.

 

·        Во всех остальных случаях количество групп остаётся неизменным.

 

Для обработки запроса типа t = 2 достаточно вывести текущее значение переменной cnt.

 

Пример

 

 

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

Объявим структуру данных map.

 

map<int, int> m;

 

Читаем количество компьютеров n и количество запросов q.

 

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

 

Инициализируем фиктивные компьютеры с номерами 0 и n + 1.

 

m[0] = 1;

m[n + 1] = 1;

 

Количество групп компьютеров в сети будем поддерживать в переменной cnt. Изначально все компьютеры рабочие, поэтому cnt = 1.

 

cnt = 1;

 

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

 

while (q--)

{

  scanf("%d", &t);

  if (t == 1)

  {

 

Запрос t = 1. Компьютер с номером l выходит из строя. Если компьютер l уже был сломан, никаких действий не требуется.

 

    scanf("%d", &l);

    if (m[l] == 0)

    {

 

В противном случае устанавливаем состояние компьютера l как сломанное.

 

      m[l] = 1;

 

В зависимости от состояния соседних с l компьютеров (рабочих или сломанных) пересчитываем количество групп:

·        Если оба соседних компьютера сломаны, то уменьшаем cnt на 1;

·        Если оба соседних компьютера рабочие, то увеличиваем cnt на 1;

 

      k = m[l - 1] + m[l + 1];

      if (k == 2) cnt--;

      else if (k == 0) cnt++;

    }

  }

  else

 

Для запроса t = 2 выводим текущее количество групп компьютеров в сети.

 

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

}