Codechef Long Challenge problem DISTNUM3

Блог пользователя rhezo

Автор rhezo, история, 7 лет назад, По-английски

How to solve this problem?

Statement: Given N nodes of a tree, answer Q queries of 2 types(update value of some node or find the number of distinct numbers on the path from U to V).

There is a solution with Mo's algorithm with updates and I don't understand that as well. Can anyone explain any other approach or even this one?

rhezo
7 лет назад
10

Комментарии (10)

Написать комментарий?

rhezo

7 лет назад, # |

Auto comment: topic has been updated by rhezo (previous revision, new revision, compare).

→ Ответить

AGHORii

7 лет назад, # |

+15

Update query on Mo
Mo on trees
Maybe these links can help you.

→ Ответить

rajat1603

7 лет назад, # |

← Rev. 2 →

+23

Perform a DFS of the tree and obtain the dfs start and end times , if a query is from $\text{[math]}$ to $\text{[math]}$ , let $\text{[math]}$ . Assume $\text{[math]}$ . If $\text{[math]}$ then query is from $\text{[math]}$ to $\text{[math]}$ else query is from $\text{[math]}$ to $\text{[math]}$ along with $\text{[math]}$ . You need the frequency of elements from this range whos nodes appear exactly once in the range , to do that , break the array into $\text{[math]}$ blocks , and for each pair of blocks , calculate the frequency table ans the answer for that block. Now each query can be brocken in to a prefix + a pair of block + a suffix. The size of the prefix and suffix is atmost $\text{[math]}$ So add those elements by brute. To do an update traverse each pair once and update the frequency table accordingly. Total Complexity $\text{[math]}$ .

→ Ответить

gvaibhav21

7 лет назад, # ^ |

The problem is almost the same as this problem, and can be solved with the same complexity in a manner very similar to Mo's algorithm by sorting the queries via <starting block, ending block, time of query>, where starting and ending blocks are the blocks which the first and last elements of the query belong to, respectively. Code for this problem: Link.

→ Ответить

shyambs

7 лет назад, # ^ |

I understood the entire logic from your code but I have one doubt about the update queries. If the queries are given in this order :

RQ1, RQ2, UP1, UP2, UP3, UP4, RQ3, RQ4
(RQ is a range query and UP is an update query).

When the range queries are sorted if the order we get is :

RQ3, RQ1, RQ4, RQ2,

then all the update queries will be processed for every range query. This would lead to O(Q^2).

Please correct me if I am wrong.

→ Ответить

gvaibhav21

7 лет назад, # ^ |

All range queries are sorted according to the tuple: <starting block, ending block, time of query> ( meaning first sort by starting block, then by ending block, and finally by time of query. ) Notice that the number of distinct values of the tuple <starting block, ending block> are N^2 / 3, and all Range Queries with the same value of <starting block, ending block> will be sorted in the increasing order of time of query. The Q updates need to be processed only once for this group of queries. Hence total number of times we need to perform update is: Q * N^2 / 3 , not Q² . You can refer code to see how to perform these updates.

→ Ответить