 # Minimum/maximum sum of range query sum

Problem Statement :

Given an array, A : [a_0, .., a_{(n-1)}] with n elements
and q range queries each of the form [(l_0, r_0), ..., (l_{q-1}, r_{q-1})]

1. Rearrange the array A such that
\sum_{i = 0}^{q-1} \sum_{j=l_i}^{r_i} a_j is maximum and return that value
i.e, maximize sum of range query sums.

2. Rearrange the array A such that
\sum_{i = 0}^{q-1} \sum_{j=l_i}^{r_i} a_j is minimum and return that value
i.e, minimize sum of range query sums.

Constraints :

-10^9 \le a_i \le 10^9 \\ 1 \le n \le 10^5

Solution Approach :

1. Iterate over each range query and count how many times each index of the array is taken into the sum
vector<pair<int, int>> counter;
for(i=0;i<n;++i)
counter.push_back(make_pair(i, 0));

for(i=0;i<q;++i)
{
l = queries[i].first;
r = queries[i].second;
// how to take count without iterating each range ????
for(j=l;j<=r;++j)
{
counter[j].second++;
}

}

1. Sort the counter vector according to its value and sort array A in ascending order
bool sortbysec(const pair<int,int> &a,
const pair<int,int> &b)
{
return (a.second < b.second);
}
sort(counter.begin(), counter.end(), sortbysec);
sort(a.begin(), a.end());

1. Iterate over the sorted counter vector and compute minimum sum
min_sum = 0;
i = 0;
for(pair<int, int> entry : counter)
{
value = entry.second;
min_sum += value*a[i];
i++;
}

1. We can do similarly for maximum sum.

Help :

How do I optimize 1st step, i.e, find occurrences without iterating each range ?

You can use discrete integration to create the count array in O(n+q) time as follows.

1. For i = 0\ldots n+1 do:
count[i] \leftarrow 0
2. For each query (l_j,r_j) where 0 \leq j \leq q-1 do:
count[l_j] \leftarrow count[l_j]+1
count[r_j+1] \leftarrow count[r_j+1] -1
3. For i = 1\ldots n+1 do:
count[i] \leftarrow count[i] + count[i-1]

The invariant after this procedure should be as follows.

1. count = count[n+1] = 0
2. 0 \leq count[i] \leq q, for all 1 \leq i \leq n, is the number of queries that include index i .
1 Like