i have solved this using persistent segment trees and my complexity is : Q(log N)^2 but it still gives TLE!!
i have tried fast IO but it does not work…can someone help me with this…
without fast IO : CodeChef: Practical coding for everyone
with fast IO : CodeChef: Practical coding for everyone
logic : my main logic is that the first position where the prefix sum(and sum of squares) and the suffix sum(and sum of squares) differs …if they are same (i handle the case when the two ranges are exactly same) then and only then there is only one mismatch(as the prefix sum may collide so, i take sum of squares also)…now, i have build persistent segment tree based on the position of that element in base (my base is the numbers from 1 to 100001) and in the tree i stored the sum of values, sum of square of values, and the number of elements till…and then do two binary searches (in the code foo() function) one to find the first position of difference of prefix sums and other to find the same for suffix and then just checking for their equality.
