I. Очередная задача на псп
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Правильная скобочная последовательность это строка, которая состоит только из символов «(» и «)», из которой возможно получить корректное арифметическое выражение, вставляя символы «+» и «1». Например, «», «(())» и «()()» являются правильными, а «)(» и «(()» не являются правильными скобочными последовательностями. Просто же скобочной последовательностью называется строка из символов «(» и «)».

Назовём правильностью скобочной последовательности максимальную длину её правильной скобочной подпоследовательности. Например, возьмем строку «()())((())()». Для неё правильными подпоследовательностями будут, к примеру, следующие: «$$$\color{red}{\underline{\color{red}{\text{()}}}}$$$())((())()», «$$$\color{red}{\underline{\color{red}{\text{(}}}}$$$)$$$\color{red}{\underline{\color{red}{\text{(}}}}$$$))((($$$\color{red}{\underline{\color{red}{\text{))}}}}$$$()», «$$$\color{red}{\underline{\color{red}{\text{()()}}}}$$$)$$$\color{red}{\underline{\color{red}{\text{((())}}}}$$$($$$\color{red}{\underline{\color{red}{\text{)}}}}$$$», а также другие (но поля условия слишком малы, чтобы их всех перечислить). Как видно, подпоследовательностью является наша последовательность, из которой удалили ноль или больше элементов, а порядок оставшихся не поменялся. Для данной последовательности правильность будет равна $$$10$$$ (последняя из приведённых подпоследовательностей имеет такую длину).

Дано $$$n$$$ изначально пустых скобочных последовательностей. Приходят $$$q$$$ запросов двух видов:

  • «$$$1 \ \ell \ r \ x$$$» — дописать к последовательностям на отрезке $$$[\ell, r]$$$ $$$|x|$$$ скобок. Если $$$x \gt 0$$$, то скобки открывающие, если $$$x \lt 0$$$ — закрывающие.
  • «$$$2 \ \ell \ r$$$» — вывести сумму правильностей последовательностей на отрезке $$$[\ell, r]$$$.
Входные данные

В первой строке входных данных вводится два числа $$$n$$$, $$$q$$$ ($$$1 \le n \le 5 \cdot 10^5$$$, $$$1 \le q \le 5 \cdot 10^5$$$) — количество пустых скобочных последовательностей и количество запросов.

В следующих $$$q$$$ строках вводятся числа согласно формату:

  • Вводится четыре числа «$$$1 \ \ell \ r \ x$$$», ($$$1 \le \ell,r \le n$$$, $$$1 \le |x| \le 10^6$$$)
  • Вводится три числа «$$$2 \ \ell \ r$$$», ($$$1 \le \ell,r \le n$$$)
Выходные данные

Для каждого запроса второго типа выведите сумму правильностей последовательностей на соответствующем отрезке.

Система оценки
№Доп. ограниченияБаллыНеобх. группыКомментарий
$$$n$$$$$$q$$$
$$$0$$$————Тесты из условия
$$$1$$$$$$n=1$$$—$$$6$$$——
$$$2$$$——$$$15$$$—$$$\ell_i = r_i$$$ в запросах первого типа
$$$3$$$——$$$13$$$—Баланс$$$^{\text{∗}}$$$ всех скобочных последовательностей не падает ниже $$$0$$$
$$$4$$$$$$n \le 10^4 $$$$$$q \le 10^4 $$$$$$7$$$——
$$$5$$$$$$n \le 5 \cdot 10^4 $$$$$$q \le 5 \cdot 10^4 $$$$$$5$$$$$$4$$$—
$$$6$$$$$$n \le 10^5 $$$$$$q \le 10^5 $$$$$$14$$$$$$5$$$—
$$$7$$$$$$n \le 2 \cdot 10^5 $$$$$$q \le 2 \cdot 10^5 $$$$$$10$$$$$$6$$$—
$$$8$$$$$$n \le 3 \cdot 10^5 $$$$$$q \le 3 \cdot 10^5 $$$$$$8$$$$$$7$$$—
$$$9$$$$$$n \le 4 \cdot 10^5 $$$$$$q \le 4 \cdot 10^5 $$$$$$8$$$$$$8$$$—
$$$10$$$——$$$14$$$$$$0-9$$$—

$$$^{\text{∗}}$$$Балансом скобочной последовательности считается количество открывающих $$$-$$$ количество закрывающих скобок.

Пример
Входные данные
1 11
1 1 1 1
2 1 1
1 1 1 -1
2 1 1
1 1 1 1
1 1 1 -2
1 1 1 3
1 1 1 -2
1 1 1 1
1 1 1 -1
2 1 1
Выходные данные
0
2
10
Примечание

Запросы в примере образуют строку из пояснения правильности.