# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* rishabh_0906

*rivalq*

**Preparer:***iceknight1093*

**Tester and Editorialist:**# DIFFICULTY:

1873

# PREREQUISITES:

Prefix sums

# PROBLEM:

There’s an array A, and Q queries on it. You also have an integer X, initially equal to 0.

The i-th query consists of two indices L_i and R_i.

For this query, you add A_{L_i} + A_{L_i + 1} + \ldots + A_{R_i} to X.

You’re allowed to rearrange A as you like *before* any queries are performed.

What’s the maximum possible final value of X?

# EXPLANATION:

Suppose A was fixed. Let’s look at how X is computed from a different perspective.

For each query (L_i, R_i), let’s say we *select* all the indices from L_i to R_i.

Let C_i be the number of times index i is selected across all the queries.

Then, the final value of X is simply \sum_{i=1}^N C_i \cdot A_i, that is, the sum of A_i multiplied by the number of times index i was selected; across all i.

Notice that the C_i values are completely independent of ordering of A; and depend purely on the query indices.

All the C_i values can be computed in \mathcal{O}(N + Q) time.

## How?

Let’s start with C_i = 0 for all i.

For each query (L_i, R_i), we want to add 1 to each C_j such that L_i \leq j \leq R_i.

Doing this in a bruteforce manner will take \mathcal{O}(N \cdot Q) time.

However, we can do better if we process queries *offline*.

In fact, processing many range-add updates like this offline is a standard trick, and can be done with the help of prefix sums/difference arrays.

The idea is as follows:

- Consider a new array D of length N, where D_i = C_i - C_{i-1} (treat C_0 = 0).

D is the*difference array*of C. - Note that if we know the values of array D, then finding C is easy: we have D_1 + D_2 + \ldots + D_i = (C_1 - C_0) + (C_2 - C_1) + \ldots + (C_i - C_{i-1}) = C_i - C_0 = C_i.

So, C is simply the prefix sum of the D array! - Now, look at how queries on C change D.

If we add 1 to the range from L to R of C, then:- D_L increases by 1, because D_L = C_L - C_{L-1} and the latter doesn’t change.
- D_{L+1}, D_{L+2}, \ldots, D_R all don’t change, since we’re both adding 1 and subtracting 1 from them.
- D_{R+1} decreases by 1.

So, each update on C only changes two values of D.

Maintaining this is therefore very easy: start with D filled with all zeros; and for each update (L, R), increment D_L by 1 and decrement D_{R+1} by 1.

Finally, obtain C as the prefix sum array of D.

Now, each query takes \mathcal{O}(1) work, and we compute prefix sums once at the end; for \mathcal{O}(N+Q) time in total.

Once the C_i values are known, we want to ‘match’ the values of A to them so that \sum C_i\cdot A_i is maximized.

This can be done greedily.

That is, match the highest C_i with the highest A_i, the second highest C_i with the second highest A_i, and so on.

The correctness of this follows from the Rearrangement inequality.

Implementing this is fairly straightforward: sort the C_i and A_i values in ascending order, then just match them.

To reconstruct the required array, all you need to do is keep a record of the indices of the C_i values after they’ve been sorted.

# TIME COMPLEXITY

\mathcal{O}(N\log N + Q) per test case.

# CODE:

## Preparer's code (C++)

```
#include <bits/stdc++.h>
using namespace std;
const int M = 1e9 + 7;
int solve() {
int n, q;
cin >> n >> q;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
sort(a.begin() + 1, a.end());
vector<int> w(n + 2);
while (q--) {
int l, r;
cin >> l >> r;
w[l]++;
w[r + 1]--;
}
for (int i = 1; i <= n; i++) w[i] += w[i - 1];
vector<int> ord(n + 1, 0);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin() + 1, ord.end(), [&](int i, int j) {
return w[i] < w[j];
});
long long ans = 0;
auto b = a;
for (int i = 1; i <= n; i++) {
b[ord[i]] = a[i];
ans += 1LL * w[ord[i]] * a[i];
}
cout << ans << "\n";
for (int i = 1; i <= n; i++) {
cout << b[i] << " ";
}
cout << "\n";
return 0;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
```

## Editorialist's code (Python)

```
for test in range(int(input())):
n, q = map(int, input().split())
a = sorted(list(map(int, input().split())))
ct = [0]*(n+1)
for _ in range(q):
l, r = map(int, input().split())
ct[l-1] += 1
ct[r] -= 1
for i in range(1, n): ct[i] += ct[i-1]
indices = list(range(n))
indices.sort(key = lambda i : ct[i])
ans = [0]*n
x = 0
for i in range(n):
ans[indices[i]] = a[i]
x += ct[indices[i]] * a[i]
print(x)
print(*ans)
```