题意简述
有n个城市，海拔高度互不相同。小A和小B驾驶一辆车游览这些城市，他们从某一个城市S出发，两人轮流开车（小A先开，小B后开），一直向东前进（编号大的城市在东边）。
两人有不同的游览喜好，在负责驾驶时会前往下一个自己喜欢的城市：
- 每次换小B时，会前往与当前城市海拔差距最小的城市。
- 每次换小A时，会前往与当前城市海拔差距第二小的城市。
- （当有两个城市和当前城市海拔差距一样时，选海拔较低的那个）
如果不存在下一个喜欢的城市，他们会结束旅行。另外，他们不希望驾驶总路程超过x（两城市间距离定义为海拔差），如果前往下一个城市将会超过x公里，也会结束旅行。
已知n个城市的海拔高度h[i]，有M个询问，每个询问给定起点S、总路程限制x，求两人分别能行驶的公里数。
数据范围
1 <= n, M <= 105
0 <= x <= 109
-109 <= h[i] <= 109
分析
难点1：询问数量多
这题的题意比较简单，主要问题是询问个数很多。
- 先考虑模拟的方法，复杂度将达到O(nM)，一定会超时，肯定不能模拟。
- 再考虑预处理询问（合并处理相似询问），这需要看询问间有无共性或关联。但这些询问可能会以每一个城市作为起点，比如第一个询问给定(S=1, x=50)，第二个询问给定(S=12, x=100)，可能第一个询问场景下AB旅行都结束了，还没到走第二个询问场景的起点12。可见，询问之间的关联比较难找到，这条路也不可行。
因此需要找到能够快速解答每个询问的算法，一般来说需要O（logN）级别的算法。
这时很容易联想到RMQ问题，采用动态规划空间换时间的策略，预先计算好每个起点S、每个x的结果，然后各个询问都可以秒解答。
空间换时间的思路虽然不错，然而数据中的x达到了109，预计算所有起点、所有x是不可能的。不过可以思考下降维：起点这个维度简化不了（其实这个维度的量级可以接受），只能想办法简化x这个维度了。这时容易想到将x转化为二进制，我们只需要预处理当x为2k（如20，21，22，…，216）时的结果，最后将实际的x值拆成这些幂值的组合，再对相应的结果进行合并即可。等等，这里有问题！
假设我们用f[i][j]表示从城市i出发、最多行驶2j公里时小A、小B分别行驶的里程数，怎么写状态转移方程呢？我们设想的动态规划是，把整个旅行的过程拆成多段路程，每段路程可用不同的f[s][x]来表示，最后f[s][x]=f[s1][x1]+f[s2][x2]+f[s3][x3]…（其中x=x1+x2+x3+…），因此必须把这些s衔接上。但现在f[i][j]这种状态没有表示出这一小段路程的终点在哪，实际上极有可能停在某城到某城的半路上，还没到下一城，因此不能跟另一个f[i][j]衔接。而就算我们把停在半路上的位置也记在f[i][j]里（包括下一站t、距离下一站的距离remainingx），还会遇到另两个问题：
- f[i][j]的终点处是小A在开还是小B在开呢？如果是小B在开那还好。如果是小A在开，开到t城时该换小B上了，而下一个状态f[t][j-remainingx]表示的是小A从城市t出发，搞错了人，所以f[i]和f[t]出现了衔接问题。
- 不知道remainingx这段路程将来该算小A开的还是小B开的。
要修补以上两个问题即便可行，也比较麻烦。造成这种情况是因为状态设的不够优雅。
因此最好是把小A、小B绑在一起看，把小A、小B各开一次当作一轮，以轮为阶段，这样状态衔接就很自然了。
较佳的动规做法是，用f[i][k]表示从城市i出发、行驶2k轮后小A、小B各自行驶的里程数A、B以及最后到达的城市T（共3个值）。
容易写出动态转移方程：
f[i][k].T = f[f[i][k-1].T].T
f[i][k].A = f[i][k-1].A + f[f[i][k-1].T].A
f[i][k].B = f[i][k-1].B + f[f[i][k-1].T].B
理解为，比如8（k=3）轮到达的城市就是，以4（k=2）轮后到达的城市为起点，再经过4轮到达的城市。
边界条件是k=0时，需模拟一轮A、B的行程。其中尤其要判断A是否有下一站以及B是否有下一站，若两者之一没有下一站，该状态的A距离、B距离就是0，T设为i。
注：状态的计算先后次序是：k从小到大，i从大到小。
算出所有状态后，回答询问（S，x）的算法是：
- 若x大于0，表示还可以继续前进，查找状态f[S][k]中A+B距离最接近但不超过x的状态，累积A、B的路程，并从x中减去A、B路程，再将S改为此状态中的T。
- 若找不到A+B距离不超过x的状态（即f[S][0]也不满足），检查x的距离内小A能否再开一次，如果小A能再开一次，再最后累积一次A的路程。这一步非常重要，因为现在的动规状态没有考虑小A单独走一次（半轮）的情况。
- 若状态中的T与当前S相同（或者状态中的A、B皆为0），表示小A或小B已没有下一个目的地，执行步骤2然后结束。如果这个判断不加，可能造成死循环。
至此，我们已经分析了这题最难的部分。
难点2：快速查找距离最近的2个城市
这题还有一个难点：快速找到小A、小B下一个目的地的算法。也就是查找数组中和某元素值最近的两个元素，而且要在数组元素不断增多时做到即时动态查询。
肯定不能每插入一个元素排一次序（再检查指定元素前后的值），这种在n=105时是无法接受的。
要求是查找这个元素最近两个元素，也就是要取小于这个元素的最大２个元素、大于这个元素的最小２个元素（属于朴素的区间最值问题），共4个元素（答案一定在这4个元素中），再在这４个元素中选２个。 优化下的话，先取最接近的2个，判断后，再取另1个次接近的，共取3个也ok。
容易想到的是用查找树（最好是平衡树） 来解决：这是100%正确可行的，只是考场上不可以用STL的话，手写平衡树会很浪费时间还容易错。
其次的选择是线段树＋离散化：线段树比较好写，而且添加元素、查找区间最值的复杂度同样也是O（logN）。
最好的选择是双向链表：利用这题中整个数组已知的性质，预先将整个海拔数组从小到大排序，建成双向链表，然后从第一个城市开始，每次取对应链表元素的前2个和后2个元素（对于双向链表而言，这种操作复杂度是O(1)），选出其中值最接近的，然后从双向链表删除当前城市对应的链表元素（复杂度O(1)），再处理后一个城市，依次处理。注意这里的处理顺序，不要从最后一个城市开始处理（再一个个增加），定位增加和定位删除的复杂度是完全不一样的。
推荐使用双向链表，不仅实现最简单，而且效率是最高的，两全其美。
复杂度分析
建立链表时间复杂度O（N×Log2(N)），
动规时间复杂度O（N×Log2(N)），
回答询问时间复杂度O（M×Log2(N)），
因此总时间复杂度O（(N+M)×Log2(N)）。
空间复杂度O（N×Log2(N)+N）。
关键点总结
动态规划、二进制/倍增、平衡树/链表