| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | jiangly | 3631 |
| 4 | Kevin114514 | 3574 |
| 5 | maroonrk | 3521 |
| 6 | strapple | 3515 |
| 7 | Radewoosh | 3461 |
| 8 | tourist | 3428 |
| 9 | turmax | 3378 |
| 10 | Um_nik | 3376 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 162 |
| 2 | adamant | 148 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 143 |
| 5 | errorgorn | 140 |
| 6 | cry | 138 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 10 | soullless | 133 |
Auto comment: topic has been updated by fsociety00 (previous revision, new revision, compare).
You may try a segment tree on the euler tour.You need to understand the euler tour/rmq algorithm for lca first (it can be found here https://en.wikipedia.org/wiki/Lowest_common_ancestor ).Then,build a segment tree holding the maximum value of
lev[node1]-2*lev[node2]+lev[node3]where node1 and node3 are at first occurrence,both are white and node2 can be found between them(and is not neccesarily white)-lev[x]denotes the level of node x.Of course,you need to maintain some helping values (e.g maximum oflev[node1]-2*lev[node2]) but I find this a good segment tree exercise.Finally, you get O(logn) per update.Can you please Elaborate on how to Maintain the Structure. A submission Code would be Extremely Helpful.
This function 'merges' 2 segment nodes(you now the answers for
[a;b]inB,for[b+1;c]inCand you get them for[a,c]inA.I'm sorry it isn't very explicit, but i'll try to explain which is every part of the structure.The rest of the segment tree and building euler tour is more of a prequisite and I would PM if requested, but I find the most important part here.