※ [本文轉錄自 Prob_Solve 看板 #1SKMSVJI ]
作者: vincent97198 (萌新冒險者) 看板: Prob_Solve
標題: [問題] 請教 zerojudge c260 的想法
時間: Wed Jan 30 16:58:05 2019
問題
https://zerojudge.tw/ShowProblem?problemid=c260
我的想法:
單調佇列找解
我的程式碼
https://ideone.com/A8PxXy
我的問題:
要用什麼方法才能找到全部的解呢?

補了程式碼應該不會被當成伸手文了吧

(a) 先把問題 reduce 到 「求平均值 > x 的 段數」(b) 要求解 (a) ，我們可以把每個值都減掉 x，問題就被 reduce 到「求平均值為正的段數」接著由左到右枚舉蛋糕尾端，過程中用 set 維護sums ，就能快速查詢有幾個蛋糕頭的位置合法*維護 prefix sums

謝謝我懂了

這樣每次維護是O(n)？

對誒，這樣好像不能在時限內誒

對耶，C++的set沒辦法O(logN)查詢比x小的元素數量那就把set改成 離散化 + fenwick tree 應該就可以了？謝謝你的P幣

s大可以說得更詳細一點嗎?

https://pastebin.com/bPWhThGE 概念上是這樣

每個數減掉平均上/下限 找in/decreasing pair數這些pair就是不符合的找pair數的方法可以從merge sort過程找這邊的每個數=prefix sum的array(最前面補0)有點描述錯誤 是所有數減完上/下限再做 prefix sum