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

 

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

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

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

Для лучшего понимания задачи внизу приведено пояснение к примеру.

 

Вход. В первой строке даны два целых числа n (1 ≤ n ≤ 109) и q (1 ≤ q ≤ 105). В последующих q строках даны запросы.

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

 

Выход. Для каждого запроса 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 если сломанный. Изначально положим m[i] = 0 для 1 ≤ i ≤ n. Введем два фиктивных сломанных компьютера с номерами 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;

 

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

 

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

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

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

 

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

      if (k == 2) cnt--;

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

    }

  }

  else

 

При t = 2 выводим количество групп компьютеров в сети на данный момент.

 

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

}