隨手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)，粗略估計的，理論上應該更優(?