VIJOS P1404遭遇战 所有方法中 又快又好实现的是那种啊

光分类中就给出了这么多
动态规划 树状数组 线段树 单调队列 二分查找 最短路

居然没回复
感觉这种题很经典啊
甚至有点想写自己在oj上的第一个题解了
然后 先发一下自己写出来的部分吧
----------------------------------------------------------------------------------
前段时间做费用流时做过一道类似的题 所以先想到了最短路做法
方法1：按点之间的关系建边 最多n^2条边
然后还可利用有向无环图的性质以O（n+e）的时间求出
但是空间上n^2的边存不下 所以理论上只有70分
方法2：根据坐标范围较小 可以按坐标关系建边
最多n+（e-s）条边 可以存下
至于求最短路 不知为何我的spfaTLE了（只有40）
然后就换成了手打dijkstra+堆 然后153ms
（中间WA过多次 太长时间没手打堆了）
----------------------------------------------------------------------------------
就先写这么多吧——其他方法还没做

再写两种不涉及高级数据结构的容易想到的方法
（3、4都要先按区间右端从小到大排序一边）
----------------------------------------------------------------------------------
方法3：考虑到N*2<(e-s)(尽管还是一个数量级上的，
但是至少常数会小点）可DP加离散化1000ms
（切记离散做数组要开N*2）
方法4：这个DP是有单调性的 所以可在方法3的基础上
+break优化达到100ms
----------------------------------------------------------------------------------
既然满足单调性 二分 单调队列 单调栈 什么的绝对会更快
但是LZ太弱了 这些东西基本不会自己写（除LIS+二分，
其他的只是曾经照着一些题解打过）所以还要再学学后再写

----------------------------------------------------------------------------------
方法5:：其实之前想到又单调性可break时 就应该往二分单调栈
上想的 不过还是写少了所以不敢随便用吧——写二分改了好几次
最后60ms
顺便说一下，数据随机的情况下 单调性DP nlogn 相对于
n^2+break 不会有明显优越（因为常常每层循环内几次就
break了相当于n*一个不大的常数）
----------------------------------------------------------------------------------

来来来，我来捧场，膜拜LZ。。

----------------------------------------------------------------------------------
方法6：原来单调队列的方法是按区间左端点排的
而且还要用堆来维护 （一开始还以为是排序之后
直接O（n）解决 于是一直不理解） 最后90ms解决
用堆维护单调性常数肯定会比二分查找大些
但数据随机的话 队列的长度会很小
（一般n=10^4时也就不到100的队列长度吧）
但是此题数据好像不那么随机 于是比单调栈还慢
----------------------------------------------------------------------------------

----------------------------------------------------------------------------------
方法7：每次选取最小值也可以用RMQ来做
然后RMQ的那几种方法中 BIT的常数应该小些
于是选择了BIT 即使离散了还是要75ms
----------------------------------------------------------------------------------
居然没人提供更好的方法（明明在记录里是有很多0ms的啊）