0408. Как постричь бамбук?

У Святослава есть бамбуковый сад. Он состоит из n бамбуковых стеблей. Стебли пронумерованы от 1 до n. i-тый стебель имеет высоту x_i. Раз в день, Святослав выполняет следующую операцию: он выбирает стебель с наибольшей высотой. Если таких стеблей несколько, то он выбирает из них стебель с наименьшим номером. Затем, он укорачивает стебель вдвое. Святослав любит только целые числа, поэтому, если получившаяся высота не целая, то он уменьшает её до ближайшего целого значения.

Валентину стало интересно подсчитать следующее значение: сумму высот бамбуковых стеблей с номерами в промежутке между l и r после того, как Святослав на протяжении k дней обрабатывал свой сад. Но, к сожалению, бамбук в саду уже давно выстрижен, а Святослав поглощен решением задач. Поэтому он дал Валентину только список высот стеблей до первой операции.

Но Валентин слишком ленив. Поэтому он попросил вас помочь ему в рассчетах.

Формат входного файла

В первой строке входного файла содержатся целое число n – количество бамбуковых стеблей в саду у Святослава 1 ≤ n ≤ 10⁵. Во второй строке содержится x – список высот стеблей до того, как Святослав начал их обрезать 0 ≤ x_i ≤ 2³¹-1. В третьей строке содержится целое число m – количество запросов 1 ≤ m ≤ 10⁵. В следующих m строках содержатся запросы вида: l, r, k. l, r – границы промежутка, которым интересуется Валентин. k – количество дней, на протяжении которых Святослав обрабатывал стебли 1 ≤ l, r ≤ n, 0 ≤ k ≤ 10¹⁸.

Формат выходного файла

Выведите m строк. В i-той строке одно число – ответ на i-тый запрос.

Пример:

Источник: Чемпионат ПетрГУ по программированию. 1 марта 2015 года

Обсудить       Отправить решение



Версия для печати