Difficulty : Medium Approach for subtask1 and subtask2 (Brute Force) : For query of type 2, copy the elements a[l]...a[r] (both inclusive) into a temporary array, say S. Sort this array in descending order. Starting from the first element, find the first three consecutive elements which can form a valid triangle i.e. if the three sides are a,b and c, then, Time Complexity : $O(N^2\log_{2}N)$ Analysis for subtask3 : For a list of sides to not form a valid triangle, the side length must be such that when the sides are sorted, every element is atleast the sum of previous two elements. In the worst case, the values may be of the form: Approach : For example, say there are two vectors, v1 and v2, for the two children. Keep two pointers p1 and p2, one for each vector, initialized to $0$. Add the smaller element out of v1[p1] and v2[p2] to our temporary array and increment the corresponding pointer. If one of the list exhausts, add the remaining elements of the other list to the temporary array. It's important to know that the total number of elements in the temporary array will not be greater than 90. Now, starting from the third element from the last, travel linearly to find the first set of three consecutive elements which form a valid triangle. Say elements T[i],T[i+1] and T[i+2] form a valid triangle. Store the elements from T[i] till the end of array in the node. It's safe to say that the side lengths smaller than T[i] will never contribute to the triangle of the largest perimeter. For query of type 1, starting from the root, traverse through to the leaf, change the value of the lone element in the leaf to the new value. Now, when travelling backwards, for each parent, perform sorted merge of the vectors of the children nodes in exactly the same manner as that in building the tree. For query of type 2, there can be three cases for each node: The span of current node is completely inside the query range: Return the vector present in the node. The span of current node intersects partially with the query range: Make a call to each of its children. Merge the two vectors it has got from its children in the same manner as dpne during building, and return the MergedSorted Vector. Now, in the main method, linearly travel from the third element from the last in the vector received to find three consecutive elements which can form a valid triangle. The sum of these three elements is our required answer. If no such trio exists, then $0$ is our answer. Time Complexity: For either type of query, in the worst case, we may have to travel to a leaf and return. This is the link to my code.
This question is marked "community wiki".
asked 12 Mar, 23:36

For a list of sides to not form a valid triangle, the side length must be such that when the sides are sorted, every element is atleast the sum of previous two elements. In the worst case, the values may be of the form: 1, 2, 3, 5, 8, 13, 21, and so on... This is nothing but the Fibonacci Series. In this series, the 44th number is 1134903170 which is greater than 109. This is an important conclusion as this means that if a node contains NO valid triangle, than it will AT MAX hold Just 43 values Thus, any node in the segment tree will hold at max 45 values where the sides are of the form: 1,1,1,2,3,5,8,13... and so on till 701408733 @awesome conclusion @harshmmodi bhaiya thanks for editorial
link
This answer is marked "community wiki".
answered 12 Mar, 23:51

Anybody tell me why its showing WA for this solution:link text answered 13 Mar, 13:28
@doramon u r getting wrong because of the size of temporary array which is b[60] set the size to 90 because u can have 45 +45 from the fibonacci series But suprisingly the last test case is timing out
(13 Mar, 14:59)
@doramon change all those 30's to 50's , 29's to 49's and 60's to 100's and run... it may work then
(13 Mar, 20:30)

Anybody plz tell me why i am getting TLE for this solution : link text answered 2 days ago
In every node of the tree, you are storing all the elements in its span. This is giving TLE. Store only those elements which form the largest valid triangle and those greater than these sides. You may read the Approach for building the segment tree written above
(21 hours ago)

Nice Editorial. For similar problems, check out yandex problem D(the last round ie (waitt.. last or the second last.. i forgot XD)). Also, Polish informatics Olympiad's problem : triangles and triangles2 answered 15 hours ago
