故事起源
山上长满了三叶草，有N只牛，每只牛只喜欢某一个范围的三叶草。把山看成一个数轴，则每只牛喜欢的三叶草范围可以用一个区间[si,ei]来表示。如果一只牛i喜欢的范围大于另一只牛j，则认为牛i比牛j更强壮。也就是满足下面的关系。那请问对于每一只牛，有多少只牛比它更强壮呢？
分析
题意应该很好理解，其实就是给了很多个区间，求对于每一个区间，它属于多少个区间的真子集。例如下面的红色区间，被两个蓝色区间真包含。最先想到的肯定是直接遍历。对于每一个区间，遍历剩余的其它区间，O(n^2)搞定。最朴实无华的方法，效率肯定不高。那有没有更好的方案呢，这个就得继续找规律了。
找规律先看一下上面最简单的方案有没有什么问题，因为很多优秀的方法都是从最简单的方法一步一步优化出来的。
对于红色区间，我们可以很容易看出，其它区间其实没有遍历的必要，因为都在区间之外，甚至都没有交集。这个说明其实跟区间的位置有很强的关系，如果有了相对位置，就可以减少很多计算。那我们可以考虑一下，是不是能先按照区间排序，比如先按照左端点升序，左端点相同时，右端点降序。再看上面的图中，对于红包区间，可能真包含它的只会在前面的虚线区间中，后面的一定不可能，所以只需要遍历前面的即可。
这样会减少一些判断，但本质还是O(n^2)，还多了一个排序的代价。那有没有可能遍历更少，或者不遍历呢？
再想一下，其实对于红色区间来说，下面所有真包含它的虚线区间，你真的关心它的顺序吗，你只是需要知道它是否包含，即右端点的相对位置。如果先按照左端点升序，那么对于红色区间来说，前面的区间只可以分为两类。一类是右端点在它的右端点左边，另一类是在右边，知道这个数量就够了。把所有区间绕左端点竖起来，那么对于红色区间，就变成关注前面区间的上端点是在它的上端点的上面还是下面。
再跳出上面的框架来看，我们已经把一个区间[si,ei]投射到了一个二维平面中的点，si,ei即为横纵坐标。再看上面要满足的关系式，其实就是以红色为原点画出四象限，所有左上方第二象限的点都满足。所以一上来根据描述看成是区间反而走了弯路，因为区间也是二维信息，在一维数轴里面无法表示。看成是二维平面就很简单，升维是一种重要的手段，尤其在动态规划中应用非常普遍，一维不行变二维，二维不行三维，四维。。。
现在模型已经建立好了，那下一个问题就是，如何快速求出第二象限的点数量呢？
快速统计
把二维中的点投射到y轴上去，压缩成一维，这就变成了求上半块区间中点的数量。因为这个区间需要不断的修改和查询，树状数组是再适合不过了。
算法框架
对于所有的点(si,ei)，先按照si升序,si相同时按ei降序排列。在y轴上维护一个区间和，依次遍历队列中的点，并将每个点ei坐标所对应在y轴上的位置+1，再统计y轴上的区间上半块的区间和。
代码实现
6.1快排
实现一个快排模板，以后就不用再重复敲了。
6.2树状数组
6.3定义
6.4main
总结
算法的组合应用是比较难掌握的，建模的过程很难想到，只有真正理解了核心思想，应用起来才能得心应手，多思考，没有捷径。本文原创作者：小K，一个思维独特的写手。文章首发平台：微信公众号【小K算法】。