MAXSUMPERM - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: rishabh_0906
Preparer: rivalq
Tester and Editorialist: iceknight1093

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)
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 :frowning:

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.

I dont understand why this gives WA. Please help.
#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