Суммы отсортированных сумм подотрезков
Задача по программированию с проверкой онлайн
- Сложность
- Сложная
- Языки
- Python
- JavaScript
- TypeScript
- Java
- Go
- Темы
- Массивы и списки
- Поиск и сортировка
- Математика
Дан список из n положительных целых чисел. Возьмите все n·(n+1)/2 его непустых подотрезков (подряд идущих элементов), посчитайте сумму каждого и отсортируйте эти суммы по неубыванию — получится новый список с позициями от 1 до n·(n+1)/2. Например, для [2, 3, 2] суммы подотрезков равны 2, 3, 2, 5, 5, 7, а отсортированный список — [2, 2, 3, 5, 5, 7].
Для каждого запроса [l, r] (1 ≤ l ≤ r ≤ n·(n+1)/2) верните сумму элементов нового списка с позиции l по позицию r включительно. Ответы верните в порядке запросов.
Ограничения: 1 ≤ n ≤ 1500, каждый элемент от 1 до 100, запросов не больше пяти. Новый список содержит больше миллиона элементов, а ответ может не поместиться в 32 бита.
Пример: [5, 4, 3, 2, 1], [[3, 8]] → [26] (новый список начинается с 1, 2, 3, 3, 4, 5, 5, 6).
Источник: Coding Competitions Archive, kickstart/2015/round_e/sums_of_sums · © Google LLC · Apache-2.0 · условие переведено и дополнено