lichenxi111

該文被密碼保護。 閱讀全文

摘要： 反悔貪心分為反悔堆和反悔自動機，其中反悔自動機比較高級。 反悔堆 反悔堆一般維護的是當前決策中的最劣決策，如果有更優決策就會替換最劣決策，一般用堆維護。 例題：建筑搶修 如果可以修直接修，然后把消耗時間放進堆里，如果不能修就找堆里有沒有消耗時間比當前多的，替換一下一定不劣。 反悔自動機 這個比較高級 閱讀全文

該文被密碼保護。 閱讀全文

摘要： 前置：偏序問題 其實算不上前置，但是本篇是對這篇的補充。 CDQ 分治 如果你學過歸并排序，那你肯定知道歸并排序的做法是先讓前后兩部分有序，然后進行合并，這與 CDQ 的思想是差不多的。 CDQ 的整體仍然是分治，遞歸處理左右區間，但不同的是，CDQ 會考慮左區間對右區間的影響，并對于右區間或者答案 閱讀全文

摘要： 偏序問題就是一個元素有若干屬性，然后統計所有屬性都有序的數對個數。 對于此類問題，思路是先消到一維，再統計答案。 1、二位偏序 例題：逆序對 其實在開始 \(i < j\) 這一維度就已經排好序了，現在剩下 \(a_i\) 這一維，發現可以對樹狀數組上 \(a_i\) 這個點加一，\(query(a 閱讀全文