Задача №113785. Количество элементов < x и инкремент на отрезке
Для заданного массива требуется выполнить ряд запросов. Все запросы делятся на два типа. Запрос первого типа – вычислить количество элементов массива на отрезке от l до r меньших заданного числа x . Запрос второго типа – увеличить все элементы массива на отрезке от l до r на заданное число x .
В первой строке заданы два целых числа n и q – размер массива и количество запросов ( 1 ≤ n , q ≤ 2·10 5 ).
Во второй строке через пробел заданы n целых чисел - 10 9 ≤ a 1 , ..., a n ≤ 10 9 – элементы массива.
В следующих q строках содержатся запросы. Каждый из запросов имеет один из двух видов:
1 l r x – запрос количества элементов на отрезке от l до r меньших заданного числа x ( 1 ≤ l ≤ r ≤ n , - 10 9 ≤ x ≤ 10 9 ).
2 l r x – запрос инкремента на величину x на отрезке от l до r ( 1 ≤ l ≤ r ≤ n , - 10 6 ≤ x ≤ 10 6 ).
На каждый запрос первого типа выведите в отдельной строке ответ на этот запрос.
5 3 1 2 3 4 5 1 1 5 5 2 2 4 2 1 1 5 5
4 2