21505번 - Фонари 서브태스크다국어

Улицу Подводный канал освещают $n$ фонарей, пронумерованных вдоль улицы от 1 до $n$. Один или несколько подряд стоящих фонарей назовём сегментом. Таким образом, общее количество сегментов равно $\frac{n(n+1)}{2}$. Сегмент считается исправным, если лампочки во всех фонарях этого сегмента исправны. 

С фонарями регулярно происходят события одного из двух типов:

• в каком-то сегменте из-за скачков напряжения все лампочки одновременно перегорают;
• Архиэнерго выбирает некоторый сегмент и посылает ремонтников, чтобы заменить на нем все перегоревшие лампочки на исправные.  

После каждого события мэрия города требует от Архиэнерго предоставить отчёт о количестве исправных сегментов. Для улучшения показателей работы ремонтники включают в отчёт все сегменты, которые исправны сейчас или были исправны когда-либо ранее.

Требуется написать программу, определяющую количество сегментов после каждого события, которые исправны в этот момент или были исправны когда-либо до этого события. 

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

В каждой из последующих $q$ строк содержатся описания событий в виде трёх чисел $l_i, r_i$ и $c_i$, которые означают, что после этого события все лампочки в фонарях с номерами $l_i, l_i+1, \ldots, r_i$:

• перегорают при $c_i = 0$,
• становятся исправными при $c_i = 1$.

В описаниях всех событий $1 \le l_i \le r_i \le n$, а $c_i$ принимает значение $0$ или $1$.

В первой строке выходных данных выведите единственное число --- количество исправных сегментов в начальном состоянии. Затем по одному в строке выведите $q$ чисел: для каждого из произошедших событий выведите количество сегментов, указываемых в отчёте после этого события.

• $1 \le n \le 300\,000$
• $1 \le q \le 300\,000$