隨手coding筆記 by波路特石

原題連結： http://tioj.infor.org/problems/2030 因為上一題被CDQ洗腦很久之後莫名其妙把CDQ搞懂了 就跑來寫這題了ww 首先我們知道，對於2、3的操作是 一個詢問[QL,QR]，只要雷射光的[L,R]滿足QL<=L、R<=QR就能夠造成傷害 所以這個明顯能用CDQ分治解決 問題回到第一種操作，不妨讓所有傷害落在區間內所有重複數字中最左邊的數字上 如果沒有修改，那假設一個數字位置是R，左邊有重複同樣數字的位置是L(沒有重複可定義為0) 那只要滿足QL<=L、R<=QR就「不能造成傷害」 注意到是不能造成傷害，所以再開一棵BIT紀錄屏障先把區間和硬是放進答案裡，再用扣的就和前面的雷射光是一模一樣的操作了 那我們修改的部分就剩下維護每個數字「左邊有重複同樣數字的位置」了 可以發現對於每個數字開一個set去好好維護就能達成，不過要注意右邊的數字也會一起被動到要記得修掉><

原題連結：http://tioj.infor.org/problems/1919 感動QwQ 這題卡了超久= = 大概第一篇文章出來之前就一直卡著了(? 當初剛學完CDQ分治然後這題就一直被CDQ洗腦 導致怎麼寫都多一個log... 先觀察到這看起來就很整體二分(? 但由於不能直接開資結使用區間加，會加到重複的 那我們就固定讓「拍照區間由左邊看過來還沒出現過的數字」得到錢 也就是說，對於一個田地i，如果下一個和他一樣的雇主的位置是j 那麼要使i得到錢，就必須滿足詢問區間[L,R]有 L<=i、R<j，以及i<=R 先不管i<=R，我們可以發現在固定時間的時候這是一個二維詢問問題 只要把一維排序掉(我是用左界)，另一維就能用BIT修改維護掉 那i<=R的部分就能利用前綴相減，也就是原本排序掉的左界把R<i的錢都砍掉了！ 注意到整體二分時詢問是離線的 為了不讓每個二分搜上的node都重跑一次詢問，我們可以在把問題分類到右區間時順便扣掉現在得到的錢，這樣右區間就不需要重跑mid以前的詢問了 (還有記得把BIT清空><) 二分時每一層大約 詢問帶修改QlgM，排序QlgQ+MlgM 層數lgQ層 總複雜度約O((QlgMQ+MlgM)lgQ)，粗略估計的，理論上應該更優(?

原題連結： 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:

原題連結： http://tioj.infor.org/problems/1974 這題是一階的模考題 難度在其中應該是偏易的？ 想法在於試著枚舉其中一維度，如果能在極短的時間內求出另一維度的當前最大值就能完成。 矩形只有10^5個，左右界分開看每一維度共有2*10^5個，不難發現座標範圍10^9只是一個叫你離散化的騙局(?)，兩個維度分別真正會出現不同值域的範圍只有2*10^5種而已。 因為要枚舉其中一維度，所以這個維度(我是用x)就不需要離散化，於是先對y座標離散化。 維護y座標的最大值時，可以發現如果硬是把欲枚舉x座標的矩形加進來，對於一個固定的y座標，只要把在其上的矩形加進來最後扣掉重疊的矩形就好。 利用掃描線+線段樹跟著枚舉一起跑，維護好「扣掉重疊矩形」這個動作，就能夠O(1)查詢每個x座標的極值。 線段樹總共被修改2*n次，總共複雜度O(nlgn) 由於題目的權重不存在負值，然後我沒有發現這件事@@ 如果有負值的話還要記得額外判斷十字線有一維度完全沒射中的情況，最後和0取MAX應該才是正解。

原題連結： http://codeforces.com/problemset/problem/914/D 這題我在比賽當中想到詢問O((logn)^2)的作法，雖然壓常數後過了，可是最後還是被system test卡掉QQ 不過在賽後重送一次一模一樣的code卻過了，不知道是不是伺服器負荷量問題... 原題的詢問可以視為，詢問區間內無法被x整除的數字是否超過1個。 則考慮一個gcd線段樹，query的時候在外面開一個「無法被整除數字」的計數器。 函式裡，只要有區間能被x整除就直接return，否則就持續往詢問的區間遞迴。 如果當前node是涵蓋在詢問區間裡的： case 1: l==r(node的區間只代表一個數字) 　　因為能遞迴到這裡表示一定不能整除，計數器+1 case 2: otherwise 　　暴力往下遞迴 最後在函式的開頭補上，計數器>1就直接return。 可以觀察到，會暴力遞迴到底的次數頂多只有兩次，兩次後計數器會>1，其他的待跑函式會全部return，複雜度O(logn) 總複雜度O(N+Qlogn)(不含修改，修改約O(logn*logC)，但gcd的期望值和單點修改的常數都遠比預計的小，所以可以不用在意)