Задача №112821. Фонари
Улицу Подводный канал освещают \(n\) фонарей, пронумерованных вдоль улицы от 1 до \(n\). Один или несколько подряд стоящих фонарей назовём сегментом. Таким образом, общее количество сегментов равно \(n(n+1)/2\) . Сегмент считается исправным, если лампочки во всех фонарях этого сегмента исправны.
С фонарями регулярно происходят события одного из двух типов:
• в каком-то сегменте из-за скачков напряжения все лампочки одновременно перегорают;
• Архиэнерго выбирает некоторый сегмент и посылает ремонтников, чтобы заменить на нем все перегоревшие лампочки на исправные.
После каждого события мэрия города требует от Архиэнерго предоставить отчёт о количестве исправных сегментов. Для улучшения показателей работы ремонтники включают в отчёт все сегменты, которые исправны сейчас или были исправны когда-либо ранее.
Требуется написать программу, определяющую количество сегментов после каждого события, которые исправны в этот момент или были исправны когда-либо до этого события.
В первой строке входных данных содержатся два числа \(n\) и \(q\) — количество фонарей и количество произошедших событий. Следующая строка входных данных состоит из \(n\) символов 0 и 1, описывающих начальное состояние фонарей, где 1 обозначает фонарь с исправной лампочкой, а 0 — с перегоревшей.
В каждой из последующих q строк содержатся описания событий в виде трёх чисел \(l_i\) , \(r_i\) и \(c_i\) , которые означают, что после этого события все лампочки в фонарях с номерами \(l_i\) , \(l_i\) + 1, . . . , \(r_i\) :
• перегорают при \(c_i\) = 0,
• становятся исправными при \(c_i\) = 1.
В описаниях всех событий \(1 \le l_i \le r_i \le n\), а \(c_i\) принимает значение 0 или 1.
В первой строке выходных данных выведите единственное число — количество исправных сегментов в начальном состоянии. Затем по одному в строке выведите \(q\) чисел: для каждого из произошедших событий выведите количество сегментов, указываемых в отчёте после этого события.
7 4 1100101 4 6 1 3 6 0 3 4 1 5 7 1
5 13 13 19 28