AtCoder Beginner Contest 256 Ex - I like Query Problem 解題心得 ( 題目 )
解題概念: SGB(Segment Tree Beats, 吉老師線段樹)
解題思路(要看解法的讀者可略過):一開始想到的是線段樹+懶標，但操作一就讓我停止了這個想法，接著想到利用莫隊的離線演算法來實現，但是區間這兩種操作還是很難搞定，加上這樣時間複雜度至少是O(N.sqrt(Q))，也許因為需要甚麼資結後面再多個log之類的(?，雖然這題有8s，但感覺就不可能過。
解題方法:這題的解題策略就是類似使用線段樹+懶人標記，只是因為這題的操作1並沒有一個規律性，沒辦法直接用懶人標記達成效果，但這裡可以使用的是Segment Tree Beats，就是我們暴力執行操作1，但是記得做到一塊數字都一樣的節點就停止，這裡看似時間複雜度會退化成O(NQ)，但是因為操作1有個性質: 做最多 log A_i 次 (約等於17)全部數字都會變成1，所以其實時間複雜度會接近於O(NlogN+QlogNlogA)，因此能通過。
Java solution code:
https://wtools.io/paste-code/bJ63
文章標籤
全站熱搜
