211096@stu.cchs.chc.edu.tw
(唐狗針)
學校
:
彰化縣精誠中學
編號 : 872
來源 : [61.223.79.98]
最後登入時間 ：
2024-12-01 20:39:24
感覺很線段樹，我猜是節點存子樹有多少未被技能殺到的怪物，透過這個資訊知道區間的位置，每次技能對每個節點往下更新，因為最多更新N個節點(怪物被殺後不會復活)，每次更新O(logn)(實際應該更快，因為不用每次都從根節點開始往下，只要對區間的子樹dfs更新就好了)最多也就O(nlogn)應該可以AC這題。
但我是用Treap，切下區間後往下更新子樹資訊，並且不合併被技能殺掉的區間，就能正確計算新的區間位置(Treap好棒Treap好毒
不知道有沒有其他更好(毒)的解法，應該很多資料結構都能解
pusapphire@gmail.com
(pusapphire)
學校
:
不指定學校
編號 : 612
來源 : [111.246.44.62]
最後登入時間 ：
2025-01-05 14:19:48
感覺很線段樹，我猜是節點存子樹有多少未被技能殺到的怪物，透過這個資訊知道區間的位置，每次技能對每個節點往下更新，因為最多更新N個節點(怪物被殺後不會復活)，每次更新O(logn)(實際應該更快，因為不用每次都從根節點開始往下，只要對區間的子樹dfs更新就好了)最多也就O(nlogn)應該可以AC這題。
但我是用Treap，切下區間後往下更新子樹資訊，並且不合併被技能殺掉的區間，就能正確計算新的區間位置(Treap好棒Treap好毒
不知道有沒有其他更好(毒)的解法，應該很多資料結構都能解
哈嘍 我是出這題的廢物學長
的確有不那麼毒(merge split treap)的解法喔~
新鮮出爐的題解在這裡：https://hackmd.io/@PuSaff/HkrxIpKs0
211096@stu.cchs.chc.edu.tw
(唐狗針)
學校
:
彰化縣精誠中學
編號 : 872
來源 : [61.223.79.98]
最後登入時間 ：
2024-12-01 20:39:24
感覺很線段樹，我猜是節點存子樹有多少未被技能殺到的怪物，透過這個資訊知道區間的位置，每次技能對每個節點往下更新，因為最多更新N個節點(怪物被殺後不會復活)，每次更新O(logn)(實際應該更快，因為不用每次都從根節點開始往下，只要對區間的子樹dfs更新就好了)最多也就O(nlogn)應該可以AC這題。
但我是用Treap，切下區間後往下更新子樹資訊，並且不合併被技能殺掉的區間，就能正確計算新的區間位置(Treap好棒Treap好毒
不知道有沒有其他更好(毒)的解法，應該很多資料結構都能解
哈嘍 我是出這題的廢物學長的確有不那麼毒(merge split treap)的解法喔~
新鮮出爐的題解在這裡：https://hackmd.io/@PuSaff/HkrxIpKs0
感謝學長orz
但我好像沒有權限訪問題解，點進去是403
pusapphire@gmail.com
(pusapphire)
學校
:
不指定學校
編號 : 612
來源 : [111.246.44.62]
最後登入時間 ：
2025-01-05 14:19:48
感覺很線段樹，我猜是節點存子樹有多少未被技能殺到的怪物，透過這個資訊知道區間的位置，每次技能對每個節點往下更新，因為最多更新N個節點(怪物被殺後不會復活)，每次更新O(logn)(實際應該更快，因為不用每次都從根節點開始往下，只要對區間的子樹dfs更新就好了)最多也就O(nlogn)應該可以AC這題。
但我是用Treap，切下區間後往下更新子樹資訊，並且不合併被技能殺掉的區間，就能正確計算新的區間位置(Treap好棒Treap好毒
不知道有沒有其他更好(毒)的解法，應該很多資料結構都能解
哈嘍 我是出這題的廢物學長的確有不那麼毒(merge split treap)的解法喔~
新鮮出爐的題解在這裡：https://hackmd.io/@PuSaff/HkrxIpKs0
感謝學長orz但我好像沒有權限訪問題解，點進去是403
阿 不好意思
現在開了