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[0] = 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