cdq分治

bzoj3262 陌上花開 cdq分治

Description 有n朵花,每朵花有三個屬性:花形(s)、顏色(c)、氣味(m),又三個整數表示。現要對每朵花評級,一朵花的級別是它擁有的美麗能超過的花的數量。定義一朵花A比另一朵花B要美麗,當且僅當Sa>=Sb,Ca>=Cb,Ma>=Mb。顯然,兩朵花可能有同樣的屬性。需要 […]

bzoj4553 [Tjoi2016&Heoi2016]序列

Description 佳媛姐姐過生日的時候,她的小夥伴從某寶上買了一個有趣的玩具送給他。玩具上有一個數列,數列中某些項的值 可能會變化,但同一個時刻最多隻有一個值發生變化。現在佳媛姐姐已經研究出了所有變化的可能性,她想請教你 ,能否選出一個子序列,使得在任意一種變化中,這個子序列都是不降的?請你告 […]

【集訓隊互測2013】城市規劃 (多項式求逆或分治FFT)

Description: 剛剛解決完電力網路的問題, 阿狸又被領導的任務給難住了. 剛才說過, 阿狸的國家有n 個城市, 現在國家需要在某些城市對之間建立一些貿易路線, 使得整個國家的任意兩個城市都直接或間接的連通. 為了省錢, 每兩個城市之間最多只能有一條直接的貿易路徑. 對於兩個建立路線的方案, […]

1492: [NOI2007]貨幣兌換Cash 斜率優化 CDQ分治維護凸殼

Description 小Y最近在一家金券交易所工作。該金券交易所只發行交易兩種金券:A紀念券(以下簡稱A券)和 B紀念券(以下簡稱B券)。每個持有金券的顧客都有一個自己的帳戶。金券的數目可以是一個實數。每天隨著市場的起伏波動,兩種金券都有自己當時的價值,即每一單位金券當天可以兌換的人民幣數目。我們 […]

各種有用的東西、黑科技、技巧

轉自WerKeyTom_FTD的blog 1、整體二分及cdq分治實現時,每個區間不需要單獨開佇列。可以把操作弄到一個陣列了,然後多兩個參u、v表示這個區間的操作在u~v,做完後對每個操作打標記表示是否往右區間傳即可。 2、兩個long long相乘取模怎麼辦? 第一種是快速乘,類似快速冪,複雜度多 […]