【TIOJ 1919】王老先生

原題連結：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)，粗略估計的，理論上應該更優(?