На занятиях Дима получил массив из N чисел, на котором он должен сделать Q запросов. Каждый запрос состоит из двух целых чисел L и R. Ответом на запрос служит сумма чисел с индексами от L до R включительно в исходном массиве.
Дима заметил, что уровень его радости от процесса вычислений напрямую зависит от суммарного значения всех ответов на запросы. Учитывая то, что Дима может изменить порядок элементов в массиве произвольным образом, он захотел вычислить значение максимально возможной суммы результатов всех запросов, которую он может получить таким образом.
Помогите вычислить Диме это значение!
Входные данные Первая строка входного файла INPUT.TXT содержит два целых числа N и Q (1 ≤ N, Q ≤ 10^5).
Во второй строке находится N целых чисел Ai, задающих элементы массива (1 ≤ Ai ≤10^8).
В последующих Q строках находятся пары чисел L и R (1 ≤ L ≤ R ≤ N), обозначающие границы отрезка, на котором нужно вычислять сумму элементов.
Выходные данные В единственной строке выходного файла OUTPUT.TXT выведите единственное целое число – максимально возможную сумму результатов всех запросов, которую Дима может получить.
3 4
7 3 1
1 3 2 3 3 3 2 2
31
Посмотри на вхождение каждого индекса в каждый отрезок
Посчитать как в https://codeforces.me/contest/295/problem/A и отсортировать
Дело в том, что в задаче нет обновлений элементов. Необходимо найти такую расстановку элементов, чтобы сумма сумм по каждому из запросов была максимальной.
Поэтому и надо отсортировать. И выше Sk0rlupka то же самое предлагает
Рассмотрим индекс i массива значений. Заметим, что количество раз, которое элемент с индексом i будет просуммирован к общей сумме равно количеству отрезков, содержащих этот индекс. Теперь можно сказать, что чем чаще элемент с индексом i участвует в общей сумме, тем больше должно быть его значение чтобы получить максимальную общую сумму. Осталось только реализовать:
1) Отсортируем все элементы массива значений по убыванию
2) Для каждого индекса i от 1 до N найдём количество отрезков содержащих i. Это делается, например, с помощью метода сканирующей прямой. Будем хранить результаты как пары (count; i), где count — количество отрезков содержащих i, i — сам индекс
3) Отсортируем все пары по убыванию значения count
4) Сопоставим отсортированные элементы изначального массива с индексами в отсортированных парах (то есть пусть у нас есть отсортированный массив с элементами изначального массива A и отсортированные пары pairs, рассмотрим A[j] и pairs[j], где j от 1 до N, пусть массив ans — оптимальная перестановка значений, тогда ans[pairs[j].second] = A[j])
5) Выведем ответ
Сложность решения O(n*log(n)) (Сортировка элементов массива O(n*log(n)) + Метод сканирующей прямой O(n(log(n)) (так как в нём тоже используется сортировка получаем O(n*log(n)))
Спасибо.