I have been given an array and Q queries each consisting of L,R,X(L and R are Left and right indexes of subarray (starting from 0)). In each query, we need to add X to every element between L and R in the array. And then we are given P number of operations. We need to find maximum and minimum sum.
For better clarity:
5
1 4 6 2 3
3 //Q
0 1 3 //Li at each Qi
2 2 4 //Ri at each Qi
5 6 7 //Xi at each Qi
2 //P
Here Q=3 and P=2
Now we need to select any 2 out of 3 L,R,X operations to minimize and maximize sum.
For max sum:
Consider operation 1 and 3
for operation 1: L=0,R=2 and X=5
for operation 3=L=3,R=4 and X=7
so after performing operation 1, we get ={6,9,11,2,3}
so after performing operation 3, we get ={6,9,11,9,10}
Sum of array:6+9+11+9+10=45
Similarly for minimum:
Consider operation 2 and 3
so after performing operation 2, we get ={1,10,12,2,3}
so after performing operation 3, we get ={1,10,12,9,10}
Sum=42
If someone could solve this problem apart from brute force approach and give a bit of explanation, it would be helpful.