| Codeforces Round 179 (Div. 1) |
|---|
| Закончено |
У Ярослава есть n точек, лежащих на оси Ox. Координата первой точки — x1, второй — x2, ..., n-ой — xn. Сейчас Ярослав хочет выполнить m запросов, каждый из которых одного из двух следующих типов:
- Переместить pj-тую точку из позиции xpj в позицию xpj + dj. При этом гарантируется, что после выполнения запроса ни у каких двух точек координаты не совпадут.
- Посчитать сумму расстояний между всеми парами точек, которые лежат на отрезке [lj, rj] (lj ≤ rj). Другими словами, требуется посчитать сумму:
.
Помогите Ярославу.
В первой строке содержится целое число n — количество точек (1 ≤ n ≤ 105). Во второй строке содержатся различные целые числа x1, x2, ..., xn — координаты точек (|xi| ≤ 109).
В третьей строке содержится целое число m — количество запросов (1 ≤ m ≤ 105). В следующих m строках содержатся запросы. В j-той строке сначала записано целое число tj (1 ≤ tj ≤ 2) — тип запроса. Если tj = 1, то далее записаны два целых числа pj и dj (1 ≤ pj ≤ n, |dj| ≤ 1000). Если tj = 2, то далее записаны два целых числа lj и rj ( - 109 ≤ lj ≤ rj ≤ 109).
Гарантируется, что в каждый момент времени координаты всех точек различны.
Для каждого запроса второго типа выведите ответ в отдельной строке. Ответы выводите в порядке следования запросов во входных данных.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на C++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
8
36 50 28 -75 40 -60 -95 -48
20
2 -61 29
1 5 -53
1 1 429
1 5 130
2 -101 -71
2 -69 53
1 1 404
1 5 518
2 -101 53
2 50 872
1 1 -207
2 -99 -40
1 7 -389
1 6 -171
1 2 464
1 7 -707
1 1 -730
1 1 560
2 635 644
1 7 -677
176
20
406
1046
1638
156
0
