这是我的第二道线段树的练习题。又是一天半,我太菜了。
菜=CAI=Can't AK IOI
先给你们推荐一批线段树入门题。
好了,然后再来说说做法。
45分暴力
这个因该不要讲了吧,手动模拟呀。
100分差分+树状数组
大家可以去看一看这题,就明白什么是差分+树状数组的做法了。
那题甚至可以卡掉线段树
5分线段树
我的奇葩做法
首先,把每一天当成一个要维护的值。
然后,构建出一颗线段树。
再接着,每一个订单就是一个区间减法,打标记,下传。
下传的时候只要有任意节点的data小于0,标记,再输出。
显然是个错的。
但是不知道为什么还能过一个点。
但是如果您想到了这种做法,并意识到了错误,那么您离成功已经不远了。
95分线段树
不要脸感谢mrsrz指出
首先,我们要知道上面的做法错在应该统计区间最小值,而不是区间任意值!!!
而且,我们知道对于一整个区间减C,最小值也会减C。
那么,我们每次修改完成后对于一整个区间进行统计最小值不久好了吗?
那么思路是:先打上标记,down,左右区间递归,up。
其中down是标记下传操作,up是min值更新操作。
想一想,min为什么是up而不是down?
然后就去写代码吧!
遗憾的是,有一个点被卡了。
100分线段树+卡常
你可以去读入优化,register,等等等等。
也可以点击提交上方的一个标签。
100分二分
二分才是本题的正解,但是我没有去尝试。
有兴趣的同学可以都试一试呀！
都试一试,总是有好处的！
代码
你想的太美了。
9552fb97479f2868a8a3dba14bfd6805b2eeff32