Convex hull trick, segment tree
There are n pizzerias located on positions s_i and m customers located on positions c_i. All pizzerias have distinct positions. Delivering pizza from point x_1 to point x_2 costs (x_1-x_2)^2, additionally each pizzeria has value p_i such that all pizza from that pizzeria cost additionaly p_i.
For each customer you have a list of pizzerias such that this customer won’t order from those pizzerias. You have to find for each customer amount of money they will spend for pizza delivery.
You can assume that deletion of some pizzeria will lead to splitting of pizzeria set into k+1 continuous subsets, which you can compute independently using segment tree. You should also note that inside subset it’s simply minimization of linear functions, thus you can build convex hull of corresponding linear functions in each vertex of segment tree.
First of all we should note that to deliver pizza from i-th pizzeria to any position x we will have to pay p_i+(s_i-x)^2 = (p_i+s_i^2)-2s_i \cdot x+x^2. Since coefficient near x^2 is 1 for all pizzerias we can ignore x^2 part at all and assume that we’re dealing with linear functions of cost: f_i(x) = (p_i+s_i^2)-2s_i \cdot x.
If k=0 for all queries we just have to find linear function with minimum value for set of points. Thus we certainly look for some modification of convex hull trick. To do this we should note that deletion of k pizzerias split array f_1(x),\dots,f_n(x) into k+1 subarrays. Now to find minimum possible value among remaining functions we can find it in each of these segments and return the minimum among these numbers. To answer such queries in segments we can maintain segment tree having lower envelope of functions which are met in segment of vertex. Please refer to authors solution and some tutorials on convex hull trick and merge-sort tree to understand basic concepts behind the solution. Suggested resources: Convex Hull Trick, Merge-Sort tree (“Saving the entire subarrays in each vertex” section).
You can directly find k+1 functions having minimum value in given point if you consider function a_i \cdot x + b_i as point (a_i;b_i) and instead of k+1 functions having minimum value in c_i you will have to find k+1 points having minimum scalar product with point (c_i;1). To do this you will have to build convex layers of given points and do stuff like described here. This is much harder than original solution though.
Also you may use sqrt-decomposition instead of segment tree.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.