| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 5 | -is-this-fft- | 158 |
| 6 | adamant | 157 |
| 6 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 8 | nor | 154 |
| 10 | djm03178 | 153 |
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?
Auto comment: topic has been updated by rhezo (previous revision, new revision, compare).
Update query on Mo
Mo on trees
Maybe these links can help you.
Perform a DFS of the tree and obtain the dfs start and end times , if a query is from
to 
, let 
. Assume 
. If 
then query is from 
to 
else query is from 
to 
along with 
. You need the frequency of elements from this range whos nodes appear exactly once in the range , to do that , break the array into 
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 
So add those elements by brute. To do an update traverse each pair once and update the frequency table accordingly. Total Complexity 
.
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.
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.
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 N2 / 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 * N2 / 3 , not Q2 . You can refer code to see how to perform these updates.
Very nice explanation. Thanks a lot!
I saw your solution and understood everything! Thanks a lot :)
Hey.
Can anyone give me a link to a problem which is solvable with Mo's algoritm on array with updates? I'd like to practice this method.
https://toph.co/p/distinct-dishting