vkditya0997's blog

SQRT Decomposition Problem
By vkditya0997, history, 8 years ago, In English

Hello everyone,
I was trying this problem : Click
I couldn't get any idea. So, read the editorial.
It mentioned to square root decompose the queries and then solve the problem. I don't really get the idea behind it.
can someone, please explain?
P.S.: I know about SQRT decomposition

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
8 years ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

The idea is to process the queries in blocks of queries.

  • For every type 1 query that you get, you add the node to the queue of pending nodes. If that queue's size is already , then push all the nodes in it to the list of red nodes, perform BFS to update distances and empty the queue.
  • For every type 2 query that you get, you output the minimum among the distance precalculated in the BFS and the distance to all the nodes in the pending queue. That distance can be calculated using LCA, with the technique of 2i jumps for example.
  • To perform BFS, you push all red nodes at once and perform a regular "flood fill", so that each node gets visited only once.

Here's the code, perhaps it will make things clearer: Xenia and Tree

→ Reply