I got stuck on the “Easy Query” problem for some time now. I understand the 1st step which is to use a wavelet tree to identify the su and sv for each query, but I got TLE error when using segment tree to do the (offline) query list.
My segment tree is basically based on the unique value of ai (of course, using value compression as well). The query is sorted by left edge and then by right edge. When moving from one query to another, I remove ai that is not in the (new) query and add ones’ missing. I think this is where the TLE happens since worse case is O(n*n)
Reading BenQ’s internal solution, I could not figure out how the segment tree update is done to speed up. It seems to use binary jump, but I could not really understand it. Any further hint/explaination would be highly appreciated.