All about problems in Volume 114. If there is a thread about your problem, please use it. If not, create one with its number in the subject.
Moderator: Board moderators
You don't need to do the inversion to all nodes in the subtree. Storing some information in each node: At query time, you can decide what extra actions you should do for a node to find the correct result for that node based on the information stored at its ancestors.tobby wrote:Can you tell me how to do the "inversion" fast with segment tree?
EDIT: I think last problem of contest #3 of http://www.hsin.hr/coci/ has a similar solution, although it is simpler than this one.
I tried it with segment tree but got TLE. I don't know how to do the inversion fast.
Can you explain how you solved it with sqrt(n) X sqrt(n) table??
this is my algorithm's outline.
there are O(sqrt(n)) rows. at each query, you shouldn't process all elements in all rows that are included in this query. just record this operation on each "totally included" row. there are at most two not "totally included" rows, you can process all elements on these two rows.
there are O(sqrt(n)) row-record operations and O(2) row-processing operations. since recording a single row costs O(1) time, and processing all element in a row costs O(sqrt(n)) time, each query costs O(sqrt(n)) X O(1) + O(2) X O(sqrt(n)) = O(sqrt(n)) time.
i'm asian, sorry for my poor english, here is my email: firstname.lastname@example.org, i'm willing to send you my source code(400+ lines). btw, finally i solved it with segment tree, but this solution runs about 4.0 seconds.