# MAXSUMPERM - Editorial

Author: rishabh_0906
Preparer: rivalq
Tester and Editorialist: iceknight1093

1873

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?

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)

1 Like

can you please tell, how Ci values can be calculated in O(N+Q) time complexity?

Click on the “How ?” spoiler just below where I said that, it’s detailed there.

Thanks, learnt a very interesting technique today

1 Like
           vector<int> freq(n+1, 0);

for(int j=0;j<q;j++){
cin>>l>>r;

freq[l-1]++;
freq[r]--;
}
for (int i = 1; i <= n; ++i) {
freq[i] += freq[i-1];
}


This would be simple to understand check this once.

Thanks !

This was the crux of problem

I was trying to use segment trees to apply range update queries, and then proceed with assigning max values from the array to the most frequently used index. WA unfortunately

Yeah Segment trees were working (thanks to the constraints that were not super tight luckily). I personally myself used them: MAXSUMPERM.

Although that was not at all important to be used, simply prefix sums for range queries were enough.

#include <bits/stdc++.h>
using namespace std;

int main(){
int t;
cin>>t;
while(t–){
int n,q;
cin>>n>>q;
vector a(n);
vector <pair<int,int>> b(q);
vector <pair<int,int>> ans(n);
for(int i=0;i<n;i++){
ans[i].second=i;
}
for(int i=0;i<n;i++){
cin>>a[i];
}
sort(a.rbegin(),a.rend());
for(int i=0;i<q;i++){
cin>>b[i].first>>b[i].second;
ans[b[i].first-1].first++;
if(b[i].second!=n){
ans[b[i].second].first–;
}
}
for(int i=1;i<n;i++){
ans[i].first+=ans[i-1].first;
}
sort(ans.rbegin(),ans.rend());
long long int sum=0;
for(int i=0;i<n;i++){
sum+=a[i]*ans[i].first;
}
cout<<sum<<endl;
vector final(n);
for(int i=0;i<n;i++){
final[ans[i].second]=a[i];
}
for(auto &val:final){
cout<<val<<" ";
}
cout<<endl;
}
return 0;
}

 sum+=a[i]*ans[i].first;


a[i] and ans[i].first are ints in your code, their product might overflow.

Either change their datatypes, or do sum += 1LL * a[i] * ans[i].first to explicitly typecast.

Thank you very much! learned something new