※ [本文转录自 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