Оптимизация или Новый алгоритм для решения этой проблемы?

Я пытаюсь решить эту проблему:

Маленькая девочка имеет массив из n элементов (элементы массива индексируются начиная с 1).

Также есть «q» запросов, каждый из которых определяется парой целых чисел. li, ri (1 ≤ li ≤ ri ≤ n). Для каждого запроса нужно найти сумму элементов массива с индексами от li до ri включительно.

Маленькая девочка сочла проблему довольно скучной. Она решила изменить порядок элементов массива, прежде чем отвечать на запросы таким образом, чтобы сумма ответов на запросы была максимально возможной. Ваша задача — найти значение этой максимальной суммы.

Входные данные:

Первая строка содержит два целых числа через пробел: n (1 ≤ n ≤ 10 ^ 5) и q (1 ≤ q ≤ 10 ^ 5) — количество элементов в массиве и количество запросов соответственно.

Следующая строка содержит n разделенных пробелом целых чисел ai (1 ≤ ai ≤ 10 ^ 5) — элементы массива.

Каждая из следующих q строк содержит два целых числа через пробел li и ri (1 ≤ li ≤ ri ≤ n) — i-й запрос.

Выход:

В единственной строке выведите единственное целое число — максимальную сумму ответов на запросы после переупорядочения элементов массива.

Sample testcases:

input:
3 3
5 3 2
1 2
2 3
1 3
output
25

input
5 3
5 2 4 1 3
1 5
2 3
2 3
output
33

У меня есть знания о дереве сегментов, поэтому я применил метод отложенного распространения через дерево сегментов.

Код моего усилия:

#include <iostream>
#include <string>
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <vector>
#include <set>
#include <list>
#include <cmath>
#include <stack>
using namespace std;

#define scan(x) scanf("%d",&x)
#define print(x) printf("%d ",x)
#define println(x) printf("%d\n",x)
#define For(i,a,j,k) for (i = a; i < j; i+= k)
#define For_back(i,a,j,k) for (i = j; i >= a; i-= k)
#define SET(a,x) memset(a,x,sizeof(a))
#define mod 1000000007
#define inf 0x7fffffff
#define Max 2000000

typedef pair<int,int> pii;
typedef pair<pii,int> piii;

long long int tree[3*Max];
long long int lazy[3*Max];

void update(int node,int a,int b,int i,int j,long long int value)
{
if (lazy[node]!= 0)
{
tree[node] += lazy[node];

if (a != b)
{
lazy[2*node] += lazy[node];
lazy[2*node+1] += lazy[node];
}
lazy[node] = 0;
}
if (a > b || a > j || b < i)
return;
if (a >= i && b <= j)
{
tree[node] += value;
if (a != b)
{
lazy[2*node] += value;
lazy[2*node+1] += value;
}
return;
}
int mid = (a+b)/2;
update(2*node,a,mid,i,j,value);
update(2*node+1,mid+1,b,i,j,value);

tree[node] = (tree[2*node]+tree[2*node+1]);
}

long long int query(int node,int a,int b,int i,int j)
{
if (a> b || a > j || b < i) return 0;

if (lazy[node] != 0)
{
tree[node] += lazy[node];
if (a != b)
{
lazy[2*node] += lazy[node];
lazy[2*node+1] += lazy[node];
}
lazy[node] = 0;
}
if (a >= i && b <= j)
return tree[node];
int mid = (a+b)/2;
long long int q1 = query(2*node,a,mid,i,j);
long long int q2 = query(2*node+1,mid+1,b,i,j);

return ((q1+q2));
}
int main()
{
SET(lazy,0);
SET(tree,0);

int n,m;
cin >> n >> m;
int i,j;
int arr[n];
For(i,0,n,1)
{
cin >> arr[i];
}
sort(arr,arr+n);
For(i,0,m,1)
{
long long int num1,num2;
cin >> num1 >> num2;

update(1,0,n-1,num1-1,num2-1,1);
}
long long int my[n];
For(i,0,n,1)
{
long long int number = query(1,0,n-1,i,i);
my[i] = number;
}
sort(my,my+n);
long long int sum = 0;
For_back(i,0,n-1,1){
sum += my[i]*arr[i];
}
cout << sum << endl;
return 0;
}

Мой подход к этому был прост, просто сделать, как сказано, используя дерево сегментов и, наконец, напечатать ответ.

Мой вопрос: есть ли более простой алгоритм для этого? или я должен оптимизировать мой код дерева сегмента?