ZeroJudge i629 - 序列操作問題 解題心得 ( 題目 )
解題概念: Trie
解題方法:首先最直觀的方法是直接暴力，但那樣是O(N^2)，這題N = 2*10^5顯然不會通過，所以要想想別的方法。
可以發現這題前面的三個操作似乎用類似 set 的資料結構就可以完成，但是這裡需要 xor ，我們可以把數字轉成二進位，並把他視為一個序列，用 trie 來儲存，使用 trie 的話，對於被 xor 1的那個 bit，就等價於把兩個子節點交換，而我們可以透過維護子樹大小來查詢，最終時間複雜度為O(NlogC)。
給讀者額外的挑戰: N<=80000、把題目操作4改成"and"，其他不更動，那要怎麼做呢? (提示:O(N^2)的話大概會炸)
Java solution code:
https://wtools.io/paste-code/bEC0
文章標籤
全站熱搜
留言列表
