Hamid is visiting a fair near his village. There are N shops of toys arranged in a line from left to right numbered 1 to N. There are two types of toys in each shop. The toy of type 1 costs A[i][0] coins and the toy of type 2 costs A[i][1] coins.
Now, he asks you to solve Q queries for him.
Each query will be of type-> l r x y -> He visits each shop from l to r in this order and he will buy exactly one toy from each of the visited shops. But, he wants to buy at least x toys of type 1 and at least y toys of type 2. Help him find the minimum cost for buying the toys. Since the answer can be large, return it modulo 10^9 + 7. Problem Constraints
1 <= N, Q <= 10^5
1 <= l <= r <= N
0 <= x + y <= r-l+1
1 <= A[i][0], A[i][1] <= 10^9
Input Format
The first argument contains a 2D array A of size N x 2, denoting the prices of toys.
The second argument contains a 2D array B of size Q x 4, denoting the queries.
Output Format
Return an array of size Q denoting the answers to the queries.
Input 1:
A :
[
[1, 2]
[4, 2]
[3, 2]
[4, 3]
]
B :
[
[2, 3, 1, 1]
[1, 4, 2, 1]
]
Input 2:
A :
[
[2, 3]
[4, 5]
[2, 1]
]
B :
[
[2, 3, 0, 1]
]
Example Output
Output 1:
[5, 9]
Output 2:
[5]
I am applying segment tree and storing sorted prices of both types of toys in every node. But not sure hot to apply the x and y constraints mentioned in the query to minimize total price. Also only one toy can be purchased from a particular shop. Please suggest correct way for maintaining segment tree . Thanks in advance :)
Edit : Problem is from a contest which is completed now :)
Edit : Waiting for someone to throw some light on how to solve this problem. Please help!!
First of all, the link to the problem seems to have logged me in your account, so be careful with sharing that.
As for the problem, there might be a simpler solution, but here is what I came up with.
Let's build a sum segment tree over all costs of type 1 only. Now for a given shop $$$i$$$ we can define $$$D_i=A[i][1]-A[i][0]$$$, which defines how much we would have to pay to change our choice from type 1 to type 2 in that shop.
Now suppose we iteratively update all the costs from type 1 to their corresponding type 2 costs, but in order of increasing $$$D_i$$$ values. It is clear that all $$$D_i<0$$$ values are good for our costs (regardless of the queries) and all $$$D_i>0$$$ are bad, so define the moment after we've updated all $$$D_i<0$$$, but none others, as the "optimal moment".
Now let's look at a specific query. We consider the optimal moment:
If at the optimal moment both the $$$x$$$ and $$$y$$$ constraints are satisfied in the interval — just take the sum.
If there are not enough type 1 toys, then we need to find the latest earlier moment in which there were $$$x$$$ type 1 toys in that interval.
If there are not enough type 2 toys, then we need to find the earliest later moment in which there were $$$y$$$ type 2 toys in that interval.
The latter two cases can be solved by binary searching for the right moment.
All of this requires you to be able to easily inspect the tree at any moment for each query, so you'll need a persistent segment tree for sums. The whole solution is then:
Complexity is $$$O(NlogN + Qlog^2N)$$$. Your tree will need to support sum of costs and counting of how many of the costs in the interval are type 1 (again, just another sum).
Thanks for such a detailed explanation for this problem. I will implement the described method. Thanks a lot :)