D. Сколько не больше

2500 мс · 256 МБ · всё или ничего

Дан массив. Запросы: прибавить $x$ ко всем элементам отрезка и узнать, сколько элементов отрезка не больше заданного числа.

Формат ввода

В первой строке $n$ и $m$ ( $1 \le n, m \le 10^5$ ). Во второй строке $n$ чисел $a_i$ ( $|a_i| \le 10^9$ ).

В следующих $m$ строках запросы: 1 l r x — прибавить $x$ ( $|x| \le 10^4$ ) ко всем элементам отрезка, 2 l r x — сколько элементов отрезка не больше $x$ ( $|x| \le 2 \cdot 10^9$ ).

Формат вывода

На каждый запрос второго вида выведите ответ в отдельной строке.

Примеры

ввод

6 5
5 1 9 3 3 7
2 1 6 3
1 2 4 5
2 1 6 6
2 3 5 8
1 1 6 -100

вывод

3
3
2

ввод

1 3
1000000000
2 1 1 1000000000
1 1 1 -10000
2 1 1 -2000000000

вывод

1
0

Разбор идеи от автора задачи. Сначала попробуйте сами.

Войдите, чтобы отправлять решения.