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})]
-
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. -
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 :
- 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++;
}
}
- 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());
- 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++;
}
- We can do similarly for maximum sum.
Help :
How do I optimize 1st step, i.e, find occurrences without iterating each range ?