隨手coding筆記 by波路特石

原題連結： http://tioj.infor.org/problems/1169 首先要先想到第三子題怎麼做 對於每一個顏色，都開一棵線段樹 對於一個顏色K的線段樹維護： 1.從左邊開始不含K的最長區間 2.從右邊開始不含K的最長區間 3.這個區間不含K的最長區間 維護並不難想也不難寫，總複雜度O(2^cN+QlgN)，空間複雜度O(2^CN) 問題在當C到24時，不管是時間還是空間都有問題 我們首先觀察到，在尚未有任何氣球的時候，對於每個顏色的線段樹長相都一樣 先把原序列當成N個的單點修改操作，這樣每個修改操作一定只會到動到lgN個線段樹的節點 那這裡就可以用動態開點的方式，如果記憶體是空的表示這個區間絕對沒有該顏色，可以直接把答案填滿，這樣也不用預處理2^cN。 至於詢問操作就照原本的寫，只要注意不要讀到空的記憶體就好了 複雜度O((N+Q)lgN)，空間上如果對顏色離散化或用map會更好，不過我是直接硬開2^24個指標就是了XD

原題連結： http://tioj.infor.org/problems/1971 最近怎麼反而在練選訓題了(汗 明明根本還沒進選訓 這題一整個經典拈題 前55分有顯然的O(MN) SG Value解 比較值得提到的是後面的第三子題和第四子題 我先確定55分自己能拿之後跳過第三的12分開始想後面的33分 因為保證a_i<=20，假設我們能在這個子題實行SG Value的話 首先先觀察到所有>1的SG值都沒有用處，可以直接填上1就好了，0就還是0 於是可以觀察到，對於連續K個的區間，最多只存在2^K種區間SG 又因為第四子題a_i<=20，所以對於一個SG[i]需要呼叫的子問題絕對不低於SG[i-20]，也就是K=20 所以可以保證出現第一個重複的「大小N的區間SG」時，後面的SG結果就會和前面呈現週期性的重複 由於區間SG只有2^20種，轉換後又很方便是整數，所以可以開一個2^20的陣列紀錄每種區間SG出現的時刻 這裡還用map之類的資結絕對是中毒了(?，計算轉換的值可以邊跑邊算，所以是完完全全的O(2^N) 寫起來也不難，找到週期後記得處理一下餘數問題加前面就有88分了，似乎頗賺的(? 最讓我意外的是剩下的12分，因為我第一次拿完88分就直接卡死了只好放棄 直到最近看了某國手的文才發現，據說用O(MN)拿bitset硬開會過！？ ......然後真的過了 雖然看他的文章讓我有種我可能假解了的feel，可是看在我執行時間不算久的情況下就算了(X 結論就是，bitset真強大啊OwO~~ \

原題連結： http://tioj.infor.org/problems/1872 這題本來沒什麼想法，看題解想了好久才搞懂QQ 首先我們要先對詢問區間的右界排序(QlgQ) 然後利用差分的概念，維護序列b[i]=query(i,r)/query(i+1,r) 也就是計算詢問往左擴大一個後會需要多乘多少 這裡我是用bit維護，這樣對於一個詢問[l,r]，固定r後求得的答案就是bit_query(r)*inv(bit_query(l-1)) 維護良好的話，詢問複雜度會是QlgN 再來是維護的部分 當我們要增加一個r的時候，我們對於每個a[r]的質因數p做分開處理(質因數分解O(NlgN)) 假想r-1以前的維護都已經完成，那麼對於一個質數p，我們將會維護出一個從a[1]~a[r-1]的「嚴格遞減單調隊列」 其中內含的是a[i]中最大的p冪次因數 這時候就可以開始用一個stack做單調隊列的維護，先求出a[r]中最大的p冪次因數，冪次為c 則當top的冪次r： r<=c 該top原位置的b[i]必須被更動(因為表示這個冪次r會完全被c蓋住)，然後就可以把top拔掉了 r>c 該top原位置的b[i]必須稍做更動(增加幅度減少)，並把c推入stack後更新b[r]退出(更後面的元素我們可以相信他們已經被前面的元素更新完了) 更新b[r]、更動b[i]的部分分別一個是用乘的，一個是用除的(乘反元素) 這裡我在線篩的時候有預處理把每個質數的冪次和反元素都蓋好(複雜度NlgN)，所以更新更動都是lgN 對於每個質數，每個元素至多加入一次、拔掉一次，均攤O(1)，單一質數最慘複雜度O(NlgN) 但注意到數字最大只有10^6，所以要卡最緊也只能多約lgC個質數(實際上是更好的一個反函數)，維護總複雜度O(NlgClgN) 總複雜度O(Q(lgQ+lgN)+NlgClgN) 附上code: