Олимпиадный тренинг

Задача 29653. Поиск числа на отрезке


Задача

Темы: sqrt декомпозиция

Дан массив a длины n (\(1 <= n <= 10^6\), \(1 <= a_i <= 10^9\)). Также даны m (\(1 <= m <= 500\)) запросов вида +, l, r, k (\(1 <= l <= r <= n\), \(-10^9 <= k <= 10^9\)) и запросов вида ?, l, r, k (\(1 <= l <= r <= n\), \(-10^9 <= k <= 10^9\)).

В первом случае нужно добавить к числам на отрезке от l до r включительно, число k.
Во втором случае нужно вывести 1, если на отрезке от l до r включительно, есть число k, иначе вывести 0.

Элементы нумеруются с 1 до n.

Гарантируется, что после любого запроса любой элемент массива a лежит в диапазоне от \(-10^9\) до \(10^9\) включительно.

 

Примеры
Входные данные Выходные данные
1
5
1 2 1 1 3
3
? 1 4 3
* 2 3 2
? 1 4 3
0
1