PROBLEM LINK:
Author: Ivan Fekete DIFFICULTY:Medium PREREQUISITES:Segment tree PROBLEM:You are given an array with $N$ elements. You need to support two types of operations on this array. First one is point update. For the second operation, you will be given query range $l,r$ and you need to find the maximum possible perimeter of a triangle with nonzero area whose sides are $A_x, A_y, A_z$, where $l \le x < y < z \le r$. If no triangle can be formed, you just need to output $0$. QUICK EXPLANATION:Build a segment tree where each node stores largest $K$ elements from the interval. Value of $K$ for given constraint will be around $50$. Update function on the tree can now be supported in $O(KlogN)$. Claim: For a given range, triangle with maximum perimeter can be formed using largest $K$ elements from that interval. Answer will be 0, only for the case, when there will be less than $K$ elements in the interval and no triangle formation is possible. You can query for largest $K$ elements in $O(KlogN)$. Finding the triangle with maximum perimeter afterward is relatively easy and procedure for the same can be found in detailed explanation. EXPLANATION:Let's try to solve a simpler version first. Solve a simple version first:In this version, you are given an array of $N$ integers and you need to find the maximum possible perimeter of a triangle. Claim: If $N>K$, answer always exist and can be found using largest $K$ elements, i.e. $ i \le K $. Here $ K = O(log_{\phi}(\sqrt{5}.MAX))$, where $\phi = \frac{1+\sqrt{5}}{2}$ and $MAX$ is the maximum value which can be present in the array. If we keep on adding elements in this manner, we will end up on fibonacci sequence. Fibonacci numbers grows very fast and soon they will exceed the maximum value that can be present in the array. If we do not exceed the maximum value that can be present in the array, triangle can definitely be formed using $K$ elements. You can compute the exact value of $K$, but we will just use approximation here for our purpose: $\Rightarrow \frac{\phi^K}{\sqrt{5}} > MAX$ (Using approximation) $\Rightarrow K > log_{\phi}(\sqrt{5}.MAX)$ Conclusion: For our original purpose, we will only need largest $K$ elements from the query range. We need a Data Structure that can support point update and can report largest $K$ elements from any query range in logarithmic time complexity or similar. For current constraints $K = 50$. Using segment tree for our purposeWe can perform our required operation with the help of segment tree. In each node of segment tree, you need to store largest $K$ elements from that interval. If size of interval is less than $K$ then store all elements from that interval. Merge function for two nodes can be implemented in a manner similar to merge sort algorithm. Merging of two nodes can be done in $O(K)$. For each update/query, you will need to change/visit atmax $logN$ nodes. Hence the time complexity for each update/query will be $O(KlogN)$. For more implementation details, you can have a look at attached solutions. Time Complexity:$O(Q.K.logN)$ AUTHOR'S AND TESTER'S SOLUTIONS
This question is marked "community wiki".
asked 05 Mar '18, 18:21

I have used square root decomposition for the problem. https://www.codechef.com/viewsolution/17760397 answered 12 Mar '18, 18:59

I am not getting how this O(Q*N) submission of mine is getting 100 points. My approach : First I created a vector of pair in which i stored every element's value and index. Then I sorted this vector. For first query I used an algorithm similar to one used in insertion sort. And for query 2 I just traversed the array from backward and checked the conditions for an element, whether its index is between l and r . answered 12 Mar '18, 23:06
The only reason I can think of 
(14 Mar '18, 05:05)

Can I get a link to nice tutorial on Segment tree ? Btw I passes this question using sqrt decomposition. https://www.codechef.com/viewsolution/17743850 With little optimisation. answered 12 Mar '18, 19:25
https://www.codechef.com/viewsolution/17834749 @kailashnath199 Thank you Man. Now, i am able to do this question using segment tree. Thank You.
(14 Mar '18, 22:35)

No need to store 50 points.. while merging two arrays from child nodes.. we can break adding points when we get a triangle and by fibonacci it is clear that no. of points would be less than 50 always.. so it would be more optimized....
sample code for merging could be..
answered 12 Mar '18, 21:26

Anybody tell me why its showing WA for this solution:solution answered 13 Mar '18, 11:43

Please can someone explain to me the math involved behind the limiting the value of K to 50 ? answered 15 Mar '18, 00:35

harrypotter0 For mathematical calculations ,refer to this answered 15 Mar '18, 20:11

can anyone just tell me how setter is doing without sorting nodes. answered 17 Mar '18, 23:51

Please can someone help me in improving my solution. I have understood the concept and written a code but it is giving TLE.The complexity is Q.K.log n where k = 45. here is my code Thanks answered 26 Mar '18, 22:31

You can also simply use Max Segment Tree: Query for the largest element, remove it (by setting the value to infinity), and repeat it K times. Afterwards you just restore the values. This is also $O(K \log n)$ per query.
very nice editorial @adkroxx