求最小值变量初值不够大(INT_MAX)导致WA,引以为戒

所有的变量都要用long long。。。
最小值一定要开的足够大，开 10^10 只有75，开 10^11 才AC。。。

我是强行主席树+二分（二分一开始写跪了）。有比我更好的方法。

long long

曾经的考试题再打一遍居然发现理解错题意了WA到死...

主席树+三分强行水之。。
代码写的是二分QAQ

我是卿云鹏，我要带领数千万巨人踏平这个世界！！！

对不起国家对不起人民

什么鬼45分

回复 @TA :
那个标记其实不用管啦……不加优化也可以过的

想问楼上标记是指的什么。。
而且。。感觉常数和代码复杂度都相当高的样子。

二分答案，扫一遍求前缀和，利用前缀和O(1)计算每个区间的检验值。总时间复杂度$O((m + n) * log_2 W)$。在实现中还可以离散化所有的W，消除运行时间对参数W的依赖，还可以记录下当前已经计算到了哪一点，统计时只需添加或删除当前参数与所求参数之间的那段就可以了。这样，所有”标记“所需的时间就可以降为$O(n)$。于是总时间复杂度就变成了$O(n + mlog_2 n)$。
最后剩下一点细节：二分答案找到的Y不保证距离S最近，因此我们还要取在S另一边的一个Y做判断，输出较小的那个即可。

longint改成int64就对了 s竟然是 10^12 果然被打跪了

二分法+前缀和处理。由于随着参考系数W的增大Y单调递减显然成立，由此可以对W二分答案，在二分的过程中维护最接近s的答案ans即可。