PROBLEM LINK:Author: Misha Chorniy DIFFICULTY:EASY PREREQUISITES:Segment tree PROBLEM:You're given array $A$ of $N$ elements. You have to answer queries of two types.
QUICK EXPLANATION:The problem is equivalent to the finding element closest to $\dfrac{A_L+A_R}{2}$ on the segment $[L;R]$ and processing update queries. EXPLANATION:You have to find $A_M$ which minimizes $A_M^2(A_L+A_R)A_M+A_RA_L$. For this function we want to have $A_M$ as close as possible to the extremum of parabola which is $Z=\dfrac{A_L+A_R}{2}$. So you can reduce this to the queries of lower bound on the segment which is wellknown segment tree excercise. To solve it you have to keep multiset of all values that occur on the segment in each vertex of segment tree, this will allow you to update in $O(\log^2 N)$ by erasing old value and inserting new one in each multiset of vertices which cover position $X$. Also you can get queries in $O(\log^2 N)$ by simply asking lowerbound in each multiset of vertices you decomposed query segment in. You should also compress values, i.e. sort them and assign to each number its order in sorted sequence. This will allow to simplify algorithm and lower time and memory consumes. However one probably can solve the problem with dynamic segment tree instead of compression. Considering the compression to be done, this will look as follows:
AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here. RELATED PROBLEMS:
This question is marked "community wiki".
asked 26 Nov '17, 09:55

Why my solution is giving wrong answer on subtask #2 but correct answer on subtasks #1 and #3. https://www.codechef.com/viewsolution/16377252 answered 27 Nov '17, 17:55

Square root decomposition is also an easy and good option for this problem. answered 30 Nov '17, 22:38

https://www.codechef.com/viewsolution/16429490 only 2 subtasks of of task 1 working help followed the same approach as mentioned. answered 03 Dec '17, 14:41

@coldfire8549 I think you haven't cleared the tree vector before starting a new test case.Use vector.clear(). It will work. Happy Coding !!! :) answered 12 Dec '17, 00:37

Can somebody share the square root decomposition method for this problem here? TIA answered 04 Sep '18, 11:05
