Размещено 4 года назад по предмету Информатика от hvhlegend484

Сдать решение задачи B-Ёлка для енота
Полный балл: 30
Бонусные баллы:
Ограничение времени: 1 с
Ограничение памяти: 256M
Ёлка для енота
В стране енотов есть n городов, расположенных в ряд. Еноты любят гигантские ёлки, каждую из которых они устанавливают так, что она накрывает города с номерами в отрезке чётной длины от l до r включительно.

Ёлочным треугольником последовательности b1, ..., bk чётной длины назовём набор последовательностей Ti. Первая последовательность совпадает с данной (T1 = b1, ..., bk), а каждая из оставшихся получена удалением первого и последнего элемента из предыдущей (Ti = bi, ..., bk - i + 1). Например, ёлочный треугольник последовательности 1, 2, 3, 4, 5, 6 выглядит так:

Ёлкой последовательности c1, ..., ck чётной длины называется последовательность ёлочных треугольников последовательностей S1, ..., Sk/2, где Si = ci, ..., ck - i + 1. При этом центр каждого треугольника совпадает с центром ёлки. Например, ёлка последовательности 1, 2, 3, 4, 5, 6 выглядит так:

В каждом городе есть свой вид украшений: в i-м городе красота украшений равна ai. Когда еноты устанавливают гигантскую ёлку, накрывающую города с номерами в отрезке [l, r], то каждый город под этой ёлкой вешает свои украшения на все позиции в ёлке, под которыми этот город находится. Например, если накрыто шесть городов, то четвёртый накрытый город вешает украшения на все позиции, обозначенные четвёркой на рисунке выше.

Красота ёлки - сумма значений красоты каждого использованного украшения.

Вам даны значения красоты украшений, используемых в каждом городе, и описания k гигантских ёлок, которые ставили еноты. Енот Дмитрий хочет работать аналитиком, и в качестве тестового задания ему предложили упорядочить данный вам список из ёлок по возрастанию значений красоты. С сортировкой он справится и сам, а найти значения красоты каждой ёлки он попросил вас.

Поскольку красота ёлки может быть очень большой, достаточно найти её значение по модулю 998244353.

Формат входных данных
В первой строке задано число n (2 ≤ n ≤ 1000000) - число городов.

Во второй строке через пробел заданы n чисел a1, a2, ..., an (1 ≤ ai ≤ 109) - красота украшений, используемых в каждом из городов.

В третьей строке задано число k (1 ≤ k ≤ 1000000) - число ёлок.

В i-й из последующих k строк содержатся два числа l и r (1 ≤ l < r ≤ n) - номера первого и последнего городов, которые украшают ёлку с номером i. Гарантируется, что этот диапазон чётной длины, то есть (r - l + 1) делится на 2.

Формат результата
Необходимо вывести k строк, i-я из которых содержит суммарную красоту украшений на i-й ёлке по модулю 998244353.

Примеры
Входные данные
6
1 2 3 4 5 6
3
1 6
1 4
2 5
Результат работы
70
20
28
Входные данные
6
3 1 2 2 1 2
2
2 5
1 4
Результат работы
14
14
Примечания
Система оценки:

Решения, верно работающие при n, k ≤ 40, будут получать не менее 20% баллов. Решения, верно работающие при n, k ≤ 5000, будут получать не менее 50% баллов.

Не тот ответ на вопрос, который вам нужен?

Найди верный ответ

Самые новые вопросы

Математика - 5 лет назад

Сколько здесь прямоугольников

История - 6 лет назад

Какое управление было в древнейшем риме? как звали первого и последнего из царей рима?

Литература - 6 лет назад

Уроки французского ответе на вопрос : расскажите о герое по следующему примерному плану: 1.почему мальчик оказался в райцентре ? 2.как он чувствовал себя на новом месте? 3.почему он не убежал в деревню? 4.какие отношения сложились у него с товарищами? 5.почему он ввязался в игру за деньги? 6.как характеризуют его отношения с учительницей ? ответе на эти вопросы пожалуйста ! сочините сочинение пожалуйста

Русский язык - 6 лет назад

Русский язык - 6 лет назад

Переделай союзное предложение в предложение с бессоюзной связью. 1. океан с гулом ходил за стеной чёрными горами, и вьюга крепко свистала в отяжелевших снастях, а пароход весь дрожал. 2. множество темноватых тучек, с неясно обрисованными краями, расползались по бледно-голубому небу, а довольно крепкий ветер мчался сухой непрерывной струёй, не разгоняя зноя 3. поезд ушёл быстро, и его огни скоро исчезли, а через минуту уже не было слышно шума

Русский язык - 6 лет назад

помогите прошу!перепиши предложения, расставляя недостающие знаки препинания. объясни, что соединяет союз и. если в предложении один союз и, то во втором выпадающем списке отметь «прочерк».пример:«я шёл пешком и,/поражённый прелестью природы/, часто останавливался».союз и соединяет однородные члены.ночь уже ложилась на горы (1) и туман сырой (2) и холодный начал бродить по ущельям.союз и соединяет:1) части сложного предложенияоднородные члены,2) однородные членычасти сложного предложения—.поэт — трубач зовущий войско в битву (1) и прежде всех идущий в битву сам (ю. янонис).союз и соединяет:1) части сложного предложенияоднородные члены,2)

Физика - 6 лет назад

Вокруг прямого проводника с током (смотри рисунок) существует магнитное поле. определи направление линий этого магнитного поля в точках a и b.обрати внимание, что точки a и b находятся с разных сторон от проводника (точка a — снизу, а точка b — сверху). рисунок ниже выбери и отметь правильный ответ среди предложенных.1. в точке a — «от нас», в точке b — «к нам» 2. в точке a — «к нам», в точке b — «от нас» 3. в обеих точках «от нас»4. в обеих точках «к нам»контрольная работа по физике.прошу,не наугад важно

Информация

Посетители, находящиеся в группе Гости, не могут оставлять комментарии к данной публикации.